4 条题解
-
-31
//没问题,真的 #include<bits/stdc++.h> using namespace std; #define PI pair<int,int> struct node{ int v; int w; }; int n,m,u,v,w,s; vector<node> a[100005]; int dis[100005],h[100005]; priority_queue<PI,vector<PI>,greater<PI> > q; int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ cin>>u>>v>>w; a[u].push_back(node{v,w}); } memset(dis,0x3f,sizeof(dis)); dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()){ u=q.top().second; q.pop(); if(h[u])continue; h[u]=1; for(int i=0;i<a[u].size();i++){ v=a[u][i].v; w=a[u][i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; q.push(make_pair(dis[v],v)); } } } for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }
信息
- ID
- 475
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 520
- 已通过
- 119
- 上传者