友友们，有谁能救救孩子吗

kingcen @ 2024-10-21 22:15:24

#include<bits/stdc++.h>
#define maxn 120000
using namespace std;
int head[maxn];
int n,m,s;
int dis[maxn],book[maxn];
struct Edge
{
    int to;
    int next;
    int w;
}e[maxn*2];
int k=0;
void adde(int u,int v,int w)
{
    k++;
    e[k].to=v;
    e[k].w=w;
    e[k].next=head[u];
    head[u]=k;
}
struct ndui
{
    int id,diss;
    ndui(int id1,int dis1) 
    {
        id=id1;
        diss=dis1;
    }
    friend bool operator <(ndui x,ndui y)
    {
        x.diss>y.diss;
    }
};
priority_queue<ndui> q;
void dijkstra()
{

    int u=s;
    for(int j=1;j<n;j++)
    {
        book[u]=1;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(book[v])continue;
            if(dis[u]+e[i].w<dis[v])
            {
                dis[v]=dis[u]+e[i].w;
                q.push(ndui(v,dis[v]));
            }
        }
        while(q.size()>0&&book[q.top().id])q.pop();
        u=q.top().id;
        q.pop();
    }
}
int main()
{
    cin>>n>>m>>s;
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        adde(u,v,w);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0; 
    dijkstra();
    for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
    return 0;
}

by superLouis @ 2024-10-21 22:19:07

多少分？

by superLouis @ 2024-10-21 22:23:23

模板题，建议背下来：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3fffffff;
int n, m, s, dis[maxn];
bool vis[maxn];
vector<pair<int, int>> e[maxn];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        e[u].push_back({v, w});
    }
    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[s] = 0; vis[s] = true; 
    for (int i = 0; i < e[s].size(); i++) 
        if (dis[s] + e[s][i].second < dis[e[s][i].first]) {
            dis[e[s][i].first] = dis[s] + e[s][i].second;
            que.push( {e[s][i].second, e[s][i].first} );
        }
    while (!que.empty()) {
        int u = que.top().second; que.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int v = 0; v < e[u].size(); v++) {
            int p = e[u][v].first;
            if (dis[p] > dis[u] + e[u][v].second && !vis[p]) {
                dis[p] = dis[u] + e[u][v].second;
                que.push( {dis[p], p} );
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << (dis[i] >= inf ? 0x7fffffff : dis[i]) << " ";
    cout << "\n";
    return 0;
}

众所周知，dijkstra 是必会的算法

问：你 P3371 【模板】单源最短路径（弱化版）

by kingcen @ 2024-10-22 22:22:03

@[superLouis](/user/840824)
现在这道题AC了 P3371没过。。。