1 条题解
-
0
#include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std; const int N=200010; const int inf=0x7fffffff; int n,m,s,d[N],vis[N]; priority_queue<pair<int,int>>q; struct edge{ int w,v; }; vector<edge> e[N]; void Dijkstra(int s){ for(int i=0;i<=n;i++) d[i]=inf; d[s]=0; q.push({0,s}); while(q.size()){ auto t=q.top(); q.pop(); int u=t.second; if(vis[u]) continue; vis[u]=1; for(auto ed:e[u]){ int v=ed.v; int w=ed.w; if(d[v]>d[u]+w){ d[v]=d[u]+w; q.push({-d[v],v}); } } } return ; } int main(){ scanf("%d%d%d",&n,&m,&s); int u,v,w; while(m--){ scanf("%d%d%d",&u,&v,&w); e[u].push_back(edge{w,v}); } Dijkstra(s); for(int i=1;i<=n;i++){ printf("%d ",d[i]); } return 0; }
- 1
信息
- ID
- 2307
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 131
- 已通过
- 23
- 上传者