最短路板子

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 static const int INFTY=2147483647;
 4 const int maxm=500010;
 5 using namespace std;
 6 struct edge{
 7     int t,w,next;
 8 }e[maxm*2];
 9 ll first[maxm*2],dis[maxm*2],ent;
10 bool vis[maxm*2];
11 int n,m,s;
12 void add(int u,int v,int w)
13 {
14     e[++ent].t=v;e[ent].w=w;e[ent].next=first[u];first[u]=ent;
15 }
16 struct node{
17     int dis,pos;
18     bool operator<(const node &x)const
19     {
20         return x.dis<dis;
21     }
22 };
23 std::priority_queue<node> q;
24 void dij()
25 {
26     dis[s]=0;q.push((node){0,s});
27     while(!q.empty())
28     {
29         node tem=q.top();q.pop();
30         int x=tem.pos;
31         if(vis[x])continue;
32         vis[x]=1;
33         for(int i=first[x];i;i=e[i].next)
34         {
35             int t=e[i].t;
36             if(dis[t]>dis[x]+e[i].w)
37             {
38                 dis[t]=dis[x]+e[i].w;
39                 if(!vis[t])
40                 q.push((node){dis[t],t});
41             }
42         }
43     }
44 }
45 int main()
46 {
47     scanf( "%d%d%d", &n, &m, &s );
48     for(int i = 1; i <= n; ++i)
49     dis[i] = INFTY;
50     for(int i = 0; i < m; ++i )
51     {
52         int u, v, d;
53         scanf( "%d%d%d", &u, &v, &d );
54         add( u, v, d );
55     }
56     dij();
57     for( int i = 1; i <= n; i++ )
58         printf( "%d ", dis[i] );
59     return 0;
60 }

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 struct data{
 5     int from;
 6     int to;
 7     int w;
 8     int next;
 9 }a[500001];
10 queue<int> q;
11 bool vis[10001];
12 int first[10001];
13 ll d[10001];
14 int m,n,s,ent;
15 inline int read()
16 {
17     char ch;
18     int f=1,num=0;
19     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
20     while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
21     return f*num;
22 }
23 inline void add(int u,int v,int ww)
24 {
25     ent++;
26     a[ent].from=u;
27     a[ent].to=v;
28     a[ent].w=ww;
29     a[ent].next=first[u];
30     first[u]=ent;
31 }
32 void spfa()
33 {
34     q.push(s);
35     d[s]=0;
36     vis[s]=1;
37     while(!q.empty())
38     {
39         int h=q.front() ;
40         q.pop() ;
41         vis[h]=0;
42         for(int i=first[h];i;i=a[i].next )
43         {
44             int tt=a[i].to;
45             if(d[h]+a[i].w<d[tt])
46             {
47                 d[tt]=d[h]+a[i].w;
48                 if(!vis[tt])
49                 {
50                     q.push(tt);
51                     vis[tt]=true;
52                 }
53             }
54         }
55     } 
56 }
57 int main()
58 {
59     n=read();m=read();s=read();
60     for(int i=1;i<=m;i++)
61     {
62         int u,v,p;
63         u=read();v=read();p=read();
64         add(u,v,p);
65     }
66     for(int i=1;i<=n;i++)
67     d[i]=2147483647;
68     spfa();
69     for(int i=1;i<=n;i++)
70     printf("%lld ",d[i]);
71     return 0;
72 }