LOJ10075 农场派对

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1010;
 4 const int maxm=1e5+10;
 5 int n,m,k;
 6 struct edge
 7 {
 8     int u,v,w,nxt;
 9 }e[maxm],ee[maxm];
10 int js,jss,head[maxn],headd[maxn];
11 void addage(int u,int v,int w)
12 {
13     e[++js].u=u;e[js].v=v;e[js].w=w;
14     e[js].nxt=head[u];head[u]=js;
15 }
16 void addagee(int u,int v,int w)
17 {
18     ee[++jss].u=u;ee[jss].v=v;ee[jss].w=w;
19     ee[jss].nxt=headd[u];headd[u]=jss;
20 }
21 int diss[maxn],dis[maxn];
22 bool vis[maxn],viss[maxn];
23 struct node
24 {
25     int dis,p;
26     bool operator < (node b)const
27     {
28         return dis>b.dis;
29     }
30 };
31 void dij(int x)
32 {
33     memset(dis,0x3f,sizeof dis);
34     dis[x]=0;
35     priority_queue< node >q;
36     q.push((node){0,x});
37     while(!q.empty())
38     {
39         node t=q.top();
40         q.pop();
41         int d=t.dis,u=t.p;
42         if(vis[u])continue;
43         vis[u]=1;
44         for(int i=head[u];i;i=e[i].nxt)
45         {
46             int v=e[i].v;
47             if(dis[v]>dis[u]+e[i].w)
48             {
49                 dis[v]=dis[u]+e[i].w;
50                 q.push((node){dis[v],v});
51             }
52         }
53     }
54 }
55 void dijs(int x)
56 {
57     memset(diss,0x3f,sizeof diss);
58     diss[x]=0;
59     priority_queue<node>q;
60     q.push((node){0,x});
61     while(!q.empty())
62     {
63         node t=q.top();
64         q.pop();
65         int d=t.dis,u=t.p;
66         if(viss[u])continue;
67         viss[u]=1;
68         for(int i=headd[u];i;i=ee[i].nxt)
69         {
70             int v=ee[i].v;
71             if(diss[v]>diss[u]+ee[i].w)
72             {
73                 diss[v]=diss[u]+ee[i].w;
74                 q.push((node){diss[v],v});
75             }
76         }
77     }
78 }
79 int main()
80 {
81     scanf("%d%d%d",&n,&m,&k);
82     for(int u,v,w,i=0;i<m;++i)
83     {
84         scanf("%d%d%d",&u,&v,&w);
85         addage(u,v,w);
86         addagee(v,u,w);
87     }
88     dij(k);
89     dijs(k);
90     int ans=0;
91     for(int i=1;i<=n;++i)ans=max(ans,dis[i]+diss[i]);
92     cout<<ans;
93     return 0;
94 }