最短路求助

iamsh @ 2024-05-21 19:48:30

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 2e5 + 5;
int n,m,s,dis[N],vis[N];
vector<PII> g[N];
void dij() {
    priority_queue<PII> q;
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    q.push(make_pair(0,s));
    while(q.size()) {
        int u = q.top().second;
        q.pop();
        if(vis[u]) {
            continue;
        }
        vis[u] = 1;
        for(auto x:g[u]) {
            int v = x.second,l = x.first;
            if(dis[v] > dis[u] + l) {
                dis[v] = dis[u] + l;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&s);
    for(int i = 1;i <= m;i ++) {
        int u,v,len;
        scanf("%d%d%d",&u,&v,&len);
        g[u].push_back({len,v});
        g[v].push_back({len,u});
    }
    dij();
    for(int i = 1;i <= n;i ++) {
        printf("%d%c",dis[i]," \n"[i == n]);
    }
    return 0;
}

by CodeAnythingNow @ 2024-05-21 19:55:23

在 for 循环中读取边的信息时，将权值 len 放在前面的位置！

by CodeAnythingNow @ 2024-05-21 19:56:41

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 2e5 + 5;
int n, m, s, dis[N], vis[N];
vector<PII> g[N];

void dij() {
    priority_queue<PII> q;
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    q.push(make_pair(0, s));

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (vis[u]) {
            continue;
        }

        vis[u] = 1;

        for (auto x : g[u]) {
            int v = x.first; // 目标节点
            int l = x.second; // 边的权值

            if (dis[v] > dis[u] + l) {
                dis[v] = dis[u] + l;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &s);

    // 读取每条边信息，存储在图中
    for (int i = 0; i < m; i++) {
        int u, v, len;
        scanf("%d %d %d", &u, &v, &len);
        g[u].push_back({v, len});
    }

    // 执行 Dijkstra 算法
    dij();

    // 输出每个点的距离
    for (int i = 1; i <= n; i++) {
        printf("%d%c", dis[i], " \n"[i == n]);
    }

    return 0;
}

by CodeAnythingNow @ 2024-05-21 19:57:03

@iamsh

by iamsh @ 2024-05-21 19:58:05

谢谢！

by CodeAnythingNow @ 2024-05-21 19:58:30

len(指变量l)