gnailuyiab @ 2023-08-04 11:43:34
求求大佬帮忙看一下,找了很久没明白是哪里的问题
代码如下
#include<bits/stdc++.h>
using namespace std;
#define Vertex int
#define MaxWeight 1000000005
int dist[100005];
int visited[100005];
typedef struct node{
int v;
int w;
node(int v_, int w_): v(v_), w(w_){}
} Node;
pair<int,int> p;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater< pair<int,int> > > Heap;
vector<Node> Graph[100005];
int main(){
int n, m ,s;
cin>>n>>m>>s;
int u, v, w;
for(int i = 0; i < m; i++){
scanf("%d %d %d", &u, &v, &w);
Graph[u].push_back(node(v,w));
} //读入建立图
//Dijkstra
//初始化
for(int i = 1; i <= n; i++){
dist[i] = MaxWeight;
}
dist[s] = 0;
Heap.push(make_pair(dist[s],s));
while(!Heap.empty()){
pair<int,int> org = Heap.top(); Heap.pop();
Vertex minv = org.second;
visited[minv] = 1;
for(int i = 0; i < Graph[minv].size(); i++){
Vertex adj = Graph[minv][i].v;
int adjw = Graph[minv][i].w;
if(!visited[adj]){
dist[adj] = min(dist[adj], dist[minv]+adjw);
Heap.push(make_pair(dist[adj], adj));
}
}
}
printf("%d", 0);
for(int i = 2; i <= n; i++){
printf(" %d", dist[i]);
}
return 0;
}