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:?

1 long long spfa_slf() { 2 int n,m; 3 cin >> n >> m; 4 5 vector<pair<int,int> > edges111111; 6 for(int i = 0;i < m;i++) { 7 int x,y,w; 8 cin >> x >> y >> w; 9 edgesxx.push_back(make_pair(y,w)); 10 } 11 12 deque<int> q; 13 vector<long long> dist(n+1, ~0ULL>>1); 14 vector<bool> inQueue(n+1, false); 15 dist11 = 0; q.push_back(1); inQueue11 = true; 16 17 int doge = 0; 18 while(!q.empty()) { 19 int x = q.front(); q.pop_front(); 20 if(doge++ > C) { 21 puts("doge"); 22 return 233; 23 } 24 for(vector<pair<int,int> >::iterator it = edgesxx.begin(); 25 it != edgesxx.end();++it) { 26 int y = it->first; 27 int w = it->second; 28 if(distyy > distxx + w) { 29 distyy = distxx + w; 30 if(!inQueueyy) { 31 inQueueyy = true; 32 if(!q.empty() && distyy > distq.front()q.front()) 33 q.push_back(y); 34 else 35 q.push_front(y); 36 } 37 } 38 } 39 inQueuexx = false; 40 } 41 return distnn; 42 }

?

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:?

InputInput 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)OutputFor 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

?

圖論 ?愉悅腦洞題 卡SPFA

給了一個(gè)SPFA的SLF優(yōu)化程序，讓你把它卡掉。

這個(gè)SLF的機(jī)制大概是每次更新完，如果被更新的點(diǎn)dis比隊(duì)頭dis小，就把它插到隊(duì)頭。

根據(jù)這個(gè)性質(zhì)，只要造出數(shù)據(jù)讓它多出許多遍重復(fù)的更新即可

http://blog.csdn.net/u012221059/article/details/38336633

↑這里有張圖可以很直觀地說明問題。可以發(fā)現(xiàn)，隨著三角數(shù)量的增長，復(fù)雜度成指數(shù)級(jí)上升。

?

莫慌，不加這個(gè)鬼畜優(yōu)化的普通SPFA，復(fù)雜度上界還是$O(NM)$的

?

注釋掉的部分可以卡出一定的效果，但是卡不到指數(shù)級(jí)的樣子。

注意輸出順序也很關(guān)鍵。

那么問題來了，我為什么要花時(shí)間寫這么道沒意義的破題？

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 int main(){ 10 // freopen("in.txt","w",stdout); 11 int i,j,C; 12 while(scanf("%d",&C)!=EOF){ 13 int n=61,m=90; 14 // int n=99,m=98/2*3; 15 printf("%d %d\n",n,m); 16 /* for(i=3;i<=n;i+=2){ 17 printf("%d %d %d\n",i-2,i,-(1<<(i-1))); 18 } 19 for(i=1;i<=n-2;i+=2){ 20 printf("%d %d %d\n",i,i+1,0); 21 } 22 for(i=2;i<=n;i+=2){ 23 printf("%d %d %d\n",i,i+1,-(1<<(i-2))); 24 }*/ 25 for(i=0;i<30;i++) 26 printf("%d %d %d\n",i*2+1,i*2+2,0); 27 for(i=0;i<30;i++) 28 printf("%d %d %d\n",i*2+2,i*2+3,-(1<<(30-i))); 29 for(i=0;i<30;i++) 30 printf("%d %d %d\n",i*2+1,i*2+3,-(1<<(30-i-1))); 31 } 32 return 0; 33 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/SilverNebula/p/6710852.html

總結(jié)

以上是生活随笔為你收集整理的HDU4889 Scary Path Finding Algorithm的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。