hdu4889Scary Path Finding Algorithm【构造】搞坏spfa-slf 2014多校联合

Problem Description

Fackyyj loves the challenge phase in TwosigmaCrap(TC). One day, he meet a task asking him to find shortest path from vertex 1 to vertex n, in a graph with at most n vertices and m edges. (1 ≤ n ≤ 100,0 ≤ m ≤ n(n-1))

Fackyyj solved this problem at first glance, after that he opened someone's submission, spotted the following code:

long long spfa_slf() {
int n,m;
cin >> n >> m;

vector<pair<int,int> > edges[111];
for(int i = 0;i < m;i++) {
int x,y,w;
cin >> x >> y >> w;
edges[x].push_back(make_pair(y,w));
}

deque<int> q;
vector<long long> dist(n+1, ~0ULL>>1);
vector<bool> inQueue(n+1, false);
dist[1] = 0; q.push_back(1); inQueue[1] = true;

int doge = 0;
while(!q.empty()) {
int x = q.front(); q.pop_front();
if(doge++ > C) {
puts("doge");
return 233;
}
for(vector<pair<int,int> >::iterator it = edges[x].begin();
it != edges[x].end();++it) {
int y = it->first;
int w = it->second;
if(dist[y] > dist[x] + w) {
dist[y] = dist[x] + w;
if(!inQueue[y]) {
inQueue[y] = true;
if(!q.empty() && dist[y] > dist[q.front()])
q.push_back(y);
else
q.push_front(y);
}
}
}
inQueue[x] = false;
}
return dist[n];
}

Fackyyj's face lit up with an evil smile. He immediately clicked button "Challenge!", but due to a hard disk failure, all of his test case generators were lost! Fackyyj had no interest on recreating his precise generators, so he asked you to write one. The generator should be able to generate a test case with at most 100 vertices, and it must be able to fail the above code, i.e. let the above code print "doge". It should NOT contain any negative-cost loop.

　For those guys who doesn't know C++, Fackyyj explain the general idea of the above algorithm by the following psuedo-code:

<center>

</center>

Input

Input contains several test cases, please process till EOF.
For each test case, there will be a single line containing an integer C. It is the constant C in the above code. (C <= 23333333)

Output

For each test case, on the first line, print two integers, n and m, indicating the number of vertices and the number of edges of your graph. Next m lines, on each line print x y w, means there is a road from x to y, cost w.
1 ≤ n ≤ 100,0 ≤ m ≤ n(n-1),|w| < 2 ³¹. Note that your output shouldn't contain any negative-cost loop.

Sample Input

1

Sample Output

   4 3 1 2 1 2 3 1 3 4 1  

Author

Fudan University

Source

2014 Multi-University Training Contest 3

题意：给出spfa_slf优化的代码，要你写示例使得代码坏掉==

做法：首先应该分析这堆代码，每次拿出队首元素并弹出，查找队首元素相连的点，与现在的队首元素比较，距离比队首元素大的放到队尾，小的放到队首。每个元素跳出的次数大于给定值的时候输出”doge“。这个SLF其实对于有些数据来说是可以做到优化的，因为可以认为距离较小的点可能更新的点比较多。

造一组数据模拟一下这个过程：（就是正解）

61 90
1 2 0
3 4 0
5 6 0
7 8 0
9 10 0
11 12 0
13 14 0
15 16 0
17 18 0
19 20 0
21 22 0
23 24 0
25 26 0
27 28 0
29 30 0
31 32 0
33 34 0
35 36 0
37 38 0
39 40 0
41 42 0
43 44 0
45 46 0
47 48 0
49 50 0
51 52 0
53 54 0
55 56 0
57 58 0
59 60 0
2 3 -1073741824
4 5 -536870912
6 7 -268435456
8 9 -134217728
10 11 -67108864
12 13 -33554432
14 15 -16777216
16 17 -8388608
18 19 -4194304
20 21 -2097152
22 23 -1048576
24 25 -524288
26 27 -262144
28 29 -131072
30 31 -65536
32 33 -32768
34 35 -16384
36 37 -8192
38 39 -4096
40 41 -2048
42 43 -1024
44 45 -512
46 47 -256
48 49 -128
50 51 -64
52 53 -32
54 55 -16
56 57 -8
58 59 -4
60 61 -2
1 3 -536870912
3 5 -268435456
5 7 -134217728
7 9 -67108864
9 11 -33554432
11 13 -16777216
13 15 -8388608
15 17 -4194304
17 19 -2097152
19 21 -1048576
21 23 -524288
23 25 -262144
25 27 -131072
27 29 -65536
29 31 -32768
31 33 -16384
33 35 -8192
35 37 -4096
37 39 -2048
39 41 -1024
41 43 -512
43 45 -256
45 47 -128
47 49 -64
49 51 -32
51 53 -16
53 55 -8
55 57 -4
57 59 -2
59 61 -1

（注意加边的顺序！）

然后按着题意的操作就出来如下的结果，每行的表示当前队列中的点

front:1
2
3 2
front:3
4 2
5 4 2
front:5
6 4 2
7 6 4 2
front:7
8 6 4 2
9 8 6 4 2
front:9
10 8 6 4 2
11 10 8 6 4 2
front:11
12 10 8 6 4 2
13 12 10 8 6 4 2
front:13
14 12 10 8 6 4 2
15 14 12 10 8 6 4 2
front:15
16 14 12 10 8 6 4 2
17 16 14 12 10 8 6 4 2
front:17
18 16 14 12 10 8 6 4 2
19 18 16 14 12 10 8 6 4 2
front:19
20 18 16 14 12 10 8 6 4 2
21 20 18 16 14 12 10 8 6 4 2
front:21
22 20 18 16 14 12 10 8 6 4 2
23 22 20 18 16 14 12 10 8 6 4 2
front:23
24 22 20 18 16 14 12 10 8 6 4 2
25 24 22 20 18 16 14 12 10 8 6 4 2
front:25
26 24 22 20 18 16 14 12 10 8 6 4 2
27 26 24 22 20 18 16 14 12 10 8 6 4 2
front:27
28 26 24 22 20 18 16 14 12 10 8 6 4 2
29 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:29
30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
31 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:31
32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
33 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:33
34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
35 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:35
36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
37 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:37
38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
39 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:39
40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
41 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:41
42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
43 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:43
44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
45 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:45
46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
47 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:47
48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
49 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:49
50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
51 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:51
52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
53 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:53
54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
55 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 56 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:56
57 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:54
55 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 56 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:56
57 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:52
53 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:53
54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
55 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 56 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:56
57 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 54 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:54
55 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 56 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:56
57 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:50
51 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:51
52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
53 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:53
54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
55 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 56 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:56
57 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 54 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:54
55 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 56 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:56
57 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 52 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:52
53 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:53
54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
55 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61http://write.blog.csdn.net/postedit/51828493
front:60
61 56 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:56
57 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 54 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:54
55 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:55
56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
57 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:57
58 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
59 58 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 58 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 58 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60
61 58 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:58
59 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:59
60 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
61 60 56 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2
front:61
front:60

分析一下结果：从开头开始看每次操作相当于取出的如果是奇数，就把与其相连的偶数放到队首，然后把下一个奇数放到这个偶数前面。这样每次取出的队首都是奇数。把所有奇数遍历过一遍之后，就轮到从大到小的偶数了，偶数只连着比他大一的奇数，所以这些奇数又一次入队列了。换言之f(i)>2*f(i+2) ，那么这个复杂度就很高很高~~

再从结果分析建边方式：之所以要先写权值是0的边，因为我需要先让偶数的点入队列啊，不然+2的奇数点入队列之后偶数点就进不去了，导致+2的奇数点无法再次进入队列！

再分析思路：题中想要每个点进入队列的次数多一些，那么就要尽可能多入队列

#include <iostream>
#include<cstdio>
using namespace std;
int a;
int main()
{
 //   freopen("cin.txt","w",stdout);
    while(~scanf("%d",&a))
    {
        int t=30;
        printf("%d %d\n",t*2+1,t*3);
        for(int i=0;i<t;i++)printf("%d %d %d\n",i*2+1,2+i*2,0);

        for(int i=0;i<t;i++)printf("%d %d %d\n",2*i+1,2*i+3,-(1<<t-i-1));
        for(int i=0;i<t;i++)printf("%d %d %d\n",2*i+2,2*i+3,-(1<<t-i));
    }
    return 0;
}
//#include <algorithm>
//#include <iostream>
//#include <cstring>
//#include <cstdio>
//#include <deque>
//#include<vector>
//using namespace std;
//long long spfa_slf() {
//    int n,m;
//    cin >> n >> m;
//
//    vector<pair<int,int> > edges[111];
//    for(int i = 0;i < m;i++) {
//        int x,y,w;
//        cin >> x >> y >> w;
//        edges[x].push_back(make_pair(y,w));
//    }
//
//    deque<int> q;
//    vector<long long> dist(n+1, ~0ULL>>1);
//    vector<bool> inQueue(n+1, false);
//    dist[1] = 0; q.push_back(1); inQueue[1] = true;
//
//    int doge = 0;
//    while(!q.empty()) {
//        int x = q.front(); q.pop_front();
//        printf("front:%d\n",x);
//        if(doge++ > 200) {
//        puts("doge");
//        return 233;
//        }
//        for(vector<pair<int,int> >::iterator it = edges[x].begin();it != edges[x].end();++it) {
//            int y = it->first;
//            int w = it->second;
//            if(dist[y] > dist[x] + w) {
//                dist[y] = dist[x] + w;
//                if(!inQueue[y]) {
//                    inQueue[y] = true;
//                    if(!q.empty() && dist[y] > dist[q.front()])
//                    q.push_back(y);
//                else
//                    q.push_front(y);
//                }
//                for(int i=0;i<q.size();i++)printf("%3d",q[i]);puts("");
//               // for(int i=0;i<q.size();i++)printf("%3d",dist[q[i]]);puts("");
//            }
//        }
//        inQueue[x] = false;
//
//    }
//    return dist[n];
//}
//int main()
//{
//    freopen("cin.txt","r",stdin);
//    spfa_slf();
//    return 0;
//}