2160 农场派对

Hank

1 + 2 = 3
2 + 3 = 11
3 + 3 = 12
1 + 3 + 3 = 13

Hank

First:2160
首先，我们要读题：
N（1≤N≤1000）头牛要去参加一场在编号为x（1≤x≤N）的牛的农场举行的派对。有M（1≤M≤100000）条有向道路，每条路长Ti（1≤Ti≤100）；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这N头牛的最短路径（一个来回）中最长的一条的长度。特别提醒：可能有权值不同的重边
喔，一看，模板题！
但是，这题有一个大坑点：
有向道路
也就是说，去时的路不一定是回来的路


Second:举例


如上图，假如说所有人都到3去
那2号就直接去了，但回不来了
So,这道题需要两次DJI
一次是所有点到s的距离，一次是s到所有点的距离


Third：code

1. /*
   
2. ID: jian8281
   
3. TASK: test
   
4. LANG: C++
   
5. */
   
6. #include<cstring>
   
7. #include<cmath>
   
8. #include<cstdio>
   
9. #include<cstdlib>
   
10. #include<algorithm>
    
11. #include<iomanip>
    
12. #include<string>
    
13. #include<queue>
    
14. #include<iostream>
    
15. using namespace std;
    
16. 
    
17. #define REP(i,k,n)  for(int i=k;i<=n;i++)
    
18. #define MAXN 100010
    
19. 
    
20. int n, m, s, ans = -2147483647;
    
21. int total1, head1[MAXN], to1[MAXN], nxt1[MAXN], val1[MAXN];
    
22. int total2, head2[MAXN], to2[MAXN], nxt2[MAXN], val2[MAXN];
    
23. int dis1[MAXN];
    
24. bool vis1[MAXN];
    
25. int dis2[MAXN];
    
26. bool vis2[MAXN];
    
27. 
    
28. struct node
    
29. {
    
30.     int a;
    
31.     int b;
    
32. };
    
33. 
    
34. priority_queue<node> q;
    
35. 
    
36. bool operator < (node x,node y
    
37. ){
    
38.     return x.b > y.b;
    
39. }
    
40. 
    
41. void aadd(int a, int b, int c)
    
42. {
    
43.     total1++;
    
44.     to1[total1] = b;
    
45.     val1[total1] = c;
    
46.     nxt1[total1] = head1[a];
    
47.     head1[a] = total1;
    
48.     return;
    
49. }
    
50. 
    
51. void addd(int a,int b,int c)
    
52. {
    
53.     total2++;
    
54.     to2[total2] = b;
    
55.     val2[total2] = c;
    
56.     nxt2[total2] = head2[a];
    
57.     head2[a] = total2;
    
58.     return;
    
59. }
    
60. 
    
61. void dijkstra1()
    
62. {
    
63.     dis1[s] = 0;
    
64.      
    
65.     q.push(node{s, 0});
    
66.      
    
67.     while(!q.empty())
    
68.     {
    
69.         int u = q.top().a;
    
70.          
    
71.         q.pop();
    
72.          
    
73.         if(vis1[u])  
    
74.         {
    
75.             continue;
    
76.         }
    
77.          
    
78.         vis1[u] = true;
    
79.          
    
80.         for(int e = head1[u];e;e = nxt1[e])
    
81.         {
    
82.             if(dis1[to1[e]] > dis1[u] + val1[e])
    
83.             {
    
84.                 dis1[to1[e]] = dis1[u] + val1[e];
    
85.                 q.push(node{to1[e], dis1[to1[e]]});
    
86.             }
    
87.         }   
    
88.     }
    
89.      
    
90.     return;
    
91. }
    
92. 
    
93. void dijkstra2()
    
94. {
    
95.     dis2[s] = 0;
    
96.      
    
97.     q.push(node{s, 0});
    
98.      
    
99.     while(!q.empty())
    
100.     {
     
101.         int u = q.top().a;
     
102.          
     
103.         q.pop();
     
104.          
     
105.         if(vis2[u])  
     
106.         {
     
107.             continue;
     
108.         }
     
109.          
     
110.         vis2[u] = true;
     
111.          
     
112.         for(int e = head2[u];e;e = nxt2[e])
     
113.         {
     
114.             if(dis2[to2[e]] >  dis2[u] + val2[e])
     
115.             {
     
116.                 dis2[to2[e]] = dis2[u] + val2[e];
     
117.                 q.push(node{to2[e], dis2[to2[e]]});
     
118.             }
     
119.         }
     
120.     }
     
121.      
     
122.     return;
     
123. }
     
124. 
     
125. int main()
     
126. {
     
127.     cin >> n >> m >> s;
     
128.      
     
129.     int a, b, c;
     
130.      
     
131.     for(int i = 1;i <= m;++i)
     
132.     {
     
133.         cin>> a >> b >> c;
     
134.         aadd(a, b, c);
     
135.         addd(b, a, c);
     
136.     }
     
137.      
     
138.     for(int i = 1;i <= n;++i)
     
139.     {
     
140.         dis1[i] = dis2[i] = 2147483647;
     
141.     }
     
142.      
     
143.     dijkstra1();
     
144.     dijkstra2();
     
145.      
     
146.     for(int i = 1;i <= n;++i)
     
147.     {
     
148.         ans = max(ans, dis1[i] + dis2[i]);
     
149.     }
     
150.      
     
151.     cout << ans;
     
152. }

复制代码

caidan














































































































1.0亿