题目描述
给定一个 N 个点，M 条有向边的带非负权图，请你计算从 SS 出发，到每个点的距离。
数据保证你能从 SS出发到任意点。
输入输出格式
输入格式：
第一行为三个正整数 N, M, S。 第二行起 M 行，每行三个非负整数 u_i, v_i, w_i，表示从 u_i到 v_i有一条权值为 w_i 的边。
输出格式：
输出一行 N 个空格分隔的非负整数，表示 S 到每个点的距离。
输入输出样例
说明
1≤N≤100000；
1≤M≤200000；
S=1；
1≤ui,vi≤N；
0≤wi≤109,
0≤∑wi≤10 ^ 9。
分析：
本题就更是一道模板题了。。。但是专门卡SPFA和无堆优化的dijkstra,真是一道毒瘤题。。。所以必须敲堆优化的dijkstra。具体见下方代码。
CODE：
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 #include <algorithm> 6 #include <queue> 7 using namespace std; 8 const int M=1000005; 9 const int oo=2147483647; 10 int n,m,tot,s; 11 int next[M],head[M],to[M],adj[M],dist[M]; 12 struct node{ 13 int id,d; 14 bool operator> (const node b) const {return d>b.d;} 15 }a[M]; 16 priority_queue <node,vector<node>,greater<node> > Q; 17 void add(int u,int v,int w){ 18 next[++tot]=head[u]; 19 head[u]=tot; 20 to[tot]=v; 21 adj[tot]=w; 22 return; 23 } 24 void dijkstra(){ 25 for (int i=1;i<=n;i++) 26 dist[i]=oo; 27 dist[s]=0; 28 Q.push((node){s,0}); 29 while (!Q.empty()){ 30 node top=Q.top(); 31 Q.pop(); 32 if (top.d!=dist[top.id]) 33 continue; 34 for (int i=head[top.id];i;i=next[i]) 35 if (top.d+adj[i]<dist[to[i]]){ 36 dist[to[i]]=top.d+adj[i]; 37 Q.push((node){to[i],dist[to[i]]}); 38 } 39 } 40 return; 41 } 42 int main(){ 43 cin>>n>>m>>s; 44 for (int i=1;i<=m;i++){ 45 int u,v,w; 46 cin>>u>>v>>w; 47 add(u,v,w); 48 } 49 dijkstra(); 50 for (int i=1;i<=n;i++) 51 cout<<dist[i]<<" "; 52 return 0; 53 }