kuangbin_ShortPath S (POJ 3169)

被cow类题目弄得有些炸裂想了好久好久写了120多行依然长跪不起发现计算约束条件的时候还是好多麻烦的地方过不去

然后看了看kuangbin的blog 都是泪啊差分约束的方式做起来只要70多行啊炒鸡简洁有没有

Ps 给手写queue的实现方式跪一下真是快的飞起

------------------Update-------------------

虽然当时也感叹了一下为什么用最短路的写法解最长路但是没深究但是看了奚政巨巨的odp(什么鬼格式)之后发现原来一切都来自神奇的差分约束

约束条件是dist[i] - dist[j] <= c 等价于if(dist[i] > c + dist[j]) dist[i] 就被松弛成dist[j] + c 都是算计啊!

妙真是妙(脑补鬼畜)

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 #define INF 0x3F3F3F3F
 7 using namespace std;
 8 
 9 const int MAXN = (int)(1e4 + 10);
10 const int MAXM = (int)(1e5 + 10);
11 
12 int n, ml, md, dist[MAXN];
13 int size, head[MAXN], point[MAXM], val[MAXM], nxt[MAXM];
14 
15 void add (int from, int to, int value)
16 {
17     val[size] = value;
18     point[size] = to;
19     nxt[size] = head[from];
20     head[from] = size++;
21 }
22 
23 int  spfa()
24 {
25     int time[MAXN];//也许以后用cnt做名字比较好
26     bool vis[MAXN];
27     queue<int> q;
28     memset(vis, false, sizeof vis);
29     memset(dist, INF, sizeof dist);
30     memset(time, 0, sizeof time);
31     
32     q.push(1);
33     vis[1] = true;
34     dist[1] = 0;
35     while(!q.empty()){
36         int u = q.front();
37         q.pop();
38         vis[u] = false;
39         for(int i = head[u]; ~i; i = nxt[i]){
40             if(dist[point[i]] > dist[u] + val[i]){
41                 dist[point[i]] = dist[u] + val[i];
42                 if(!vis[point[i]]){
43                     vis[point[i]] = true;
44                     q.push(point[i]);
45                     if(++time[point[i]] > n) return -1;
46                 }
47             }
48         }
49     }
50     return dist[n] == INF ? -2 : dist[n];
51 }
52 
53 int main()
54 {
55     size = 0;
56     memset(head, -1, sizeof head);
57     
58     scanf("%d%d%d", &n, &ml, &md);
59     while(ml--){
60         int from, to, value;
61         scanf("%d%d%d", &from, &to, &value);
62         if(from > to) swap(from, to);
63         add(from, to, value);
64     }
65     while(md--){
66         int from, to, value;
67         scanf("%d%d%d", &from, &to, &value);
68         if(from < to) swap(from, to);
69         add(from, to, -value);
70     }
71     int ans = spfa();
72     printf("%d
", ans);
73     return 0;
74 }