银牛派对

题目链接：Silver Cow Party Luogu：银牛派对

我首先考虑的是跑n+1遍Dijkstra（我太蒟了）

后来还想给每条边*2....

再后来终于想到正解：

由于是有向图，那么从n-1到s的最短路不需要跑n-1次，以s为起点做一遍就够

所以要再开一个结构体，存from、to、dis，为下一步做准备，还开一个数组minn，存去、来的最短路之和

将所有数组和cnt初始化之后，再以s为起点跑一次

最后枚举最大值即可

代码：

 1 #include<iostream>
 2 #include<queue>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 const int INF = 0x7fffffff;
 8 const int N = 50005;
 9 const int M = 2000005;
10 struct edge
11 {
12     int dis,to,next;
13 }e[M];
14 int head[N],dis[N],minn[N],cnt;
15 bool vis[N];
16 int n,m,s;
17 inline void add(int u,int v,int d)
18 {
19     e[++cnt].dis=d;
20     e[cnt].to=v;
21     e[cnt].next=head[u];
22     head[u]=cnt;
23 }
24 struct node
25 {
26     int dis,pos;
27     bool operator < (const node &x) const 
28     {return x.dis<dis;}
29 };
30 struct dir
31 {
32     int to,from,d;
33 }direct[N];
34 priority_queue <node> q;
35 priority_queue <node> q2;
36 inline void Dijkstra2()
37 {
38     dis[s]=0;
39     q2.push((node){0,s});
40     while(!q2.empty())
41     {
42         node tmp=q2.top();
43         q2.pop();
44         int x=tmp.pos,d=tmp.dis;
45         if(vis[x]) continue;
46         vis[x]=1;
47         for(int i=head[x];i;i=e[i].next)
48         {
49             int y=e[i].to;
50             if(dis[y]>dis[x]+e[i].dis)
51             {
52                 dis[y]=dis[x]+e[i].dis;
53                 if(!vis[y]) q2.push((node){dis[y],y});
54             }
55         }
56     }
57 }
58 inline void Dijkstra1()
59 {
60     dis[s]=0;
61     q.push((node){0,s});
62     while(!q.empty())
63     {
64         node tmp=q.top();
65         q.pop();
66         int x=tmp.pos,d=tmp.dis;
67         if(vis[x]) continue;
68         vis[x]=1;
69         for(int i=head[x];i;i=e[i].next)
70         {
71             int y=e[i].to;
72             if(dis[y]>dis[x]+e[i].dis)
73             {
74                 dis[y]=dis[x]+e[i].dis;
75                 if(!vis[y]) q.push((node){dis[y],y});
76             }
77         }
78     }
79 }
80 int ans=-INF;
81 int main()
82 {
83     cin>>n>>m>>s;
84     for(int i=1;i<=n;++i) dis[i]=INF;
85     for(int i=0;i<m;++i)
86     {
87         cin>>direct[i].from>>direct[i].to>>direct[i].d;
88         add(direct[i].to,direct[i].from,direct[i].d);
89     }
90     Dijkstra1();
91     memset(head,0,sizeof(head));memset(e,0,sizeof(e));memset(vis,0,sizeof(vis));cnt=0;
92     for(int i=1;i<=n;++i) minn[i]=dis[i],dis[i]=INF;
93     for(int i=0;i<m;++i)
94     add(direct[i].from,direct[i].to,direct[i].d);
95     Dijkstra2();
96     for(int i=1;i<=n;++i) minn[i]+=dis[i],ans=max(ans,minn[i]);
97     cout<<ans<<endl;
98     return 0;
99 }

View Code

真不知道我是怎么想到当初那个脑残的思路的（我还是太蒟了）