1 条题解
-
0黄培钧 (huangpeijun) LV 7 @ 2022-11-13 16:23:59
/***************************************** Note: ******************************************/ #include <queue> #include <set> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int n,m,ans,i,j,k,x; int head[N],ne[N],to[N],dis[N],w[N],id,maxn; bool vis[N]; void add(int x,int y,int z) { to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id; } struct node{ int id,num; bool operator<(const node &a)const { return num>a.num; } }; void dij() { priority_queue<node>p; p.push((node){x,0}); p.push((node){x+n,0}); dis[x]=dis[n+x]=0; while(!p.empty()) { node t=p.top(); p.pop(); if(vis[t.id]||dis[t.id]!=t.num) continue; vis[t.id]=1; for(int i=head[t.id];i;i=ne[i]) { int v=to[i]; if(!vis[v]&&dis[v]>dis[t.id]+w[i]) { dis[v]=dis[t.id]+w[i]; p.push((node){v,dis[v]}); } } } } int main() { memset(dis,0x3f,sizeof vis); cin>>n>>m>>x; for(int i=1;i<=m;++i) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y+n,x+n,z); } dij(); for(int i=1;i<=n;++i) maxn=max(maxn,dis[i]+dis[i+n]); cout<<maxn; return 0; }
- 1
信息
- ID
- 412
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 32
- 已通过
- 19
- 上传者