- #include
- #include
- #include
- using namespace std;
- int n,m,S,tot,Next[500010],head[20000],tree[500010],val[500010];
- bool visit[20000];
- long long dis[20000];
- struct cmp
- {
- bool operator()(int a,int b)
- {
- return dis[a]>dis[b];
- }
- };
- priority_queue<int,vector,cmp> Q;
- void add(int x,int y,int z)
- {
- tot++;
- Next[tot]=head[x];
- head[x]=tot;
- tree[tot]=y;
- val[tot]=z;
- }
- int main()
- {
- scanf("%d%d%d",&n,&m,&S);
- tot=0;
- for (int i=1;i<=m;i++)
- {
- int x,y,z;
- scanf("%d%d%d",&x,&y,&z);
- if (x==y) continue;
- add(x,y,z);
- }
- for (int i=1;i<=n;i++)
- {
- visit[i]=false;
- dis[i]=2147483647;
- }
- Q.push(S);
- dis[S]=0;
- while (!Q.empty())
- {
- int u=Q.top();
- Q.pop();
- if (visit[u]) continue;
- visit[u]=true;
- for (int i=head[u];i;i=Next[i])
- {
- int v=tree[i];
- if (!visit[v]&&dis[v]>dis[u]+(long long)val[i])
- {
- dis[v]=dis[u]+val[i];
- Q.push(v);
- }
- }
- }
- for (int i=1;i<=n-1;i++) printf("%lld",dis[i]);
- printf("%lld\n",dis[n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3110936.html