其實這個題是抄的題解啦…… 題解給了一個圖，按照那個圖模擬一遍大概就能理解了。

題意：

　　有一段程序，給你一個C值(程序中某常量)，讓你構(gòu)造一組數(shù)據(jù)，使程序輸出"doge"
　　 那段代碼大概是 SPFA的SLF優(yōu)化。其實題目的意思是讓我們構(gòu)造一組數(shù)據(jù)，使得總的出隊次數(shù)大于C。
?? ??? ?數(shù)據(jù)范圍 C<=23,333,333。輸出的圖中最多有100個點，沒有重邊、自環(huán)、負(fù)環(huán)。


思路：

　　SLF: 設(shè)隊首元素為 i, 隊列中要加入節(jié)點 j, 在??????? 時加到隊首而不是隊尾, 否則和普通的 SPFA 一樣加到隊尾.

　　這個優(yōu)化是基于貪心的思想，因為出當(dāng)前結(jié)點的的距離越小，那么他可能更新點就越多，從而達(dá)到優(yōu)化的目的。

　　因為是貪心，我們可以“欺騙”他一下。
?? ??? ?我們可以讓距離比較大的結(jié)點加入隊列，那么他會比較晚出隊，但是，他會經(jīng)過一系列的會更新原來更新過的結(jié)點，那么被更新的點會重新入隊。那么被更新點原來的更新路徑會重新被更新一次。

　

題解：來自這里

?

代碼： 先在程序中把圖建出來，然后在輸出圖。這樣做會簡單一些。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <time.h> 15 16 using namespace std; 17 18 const int INF = 1<<30; 19 const int MAXN = 105; 20 21 int myPow(int d, int n) { 22 int res = 1; 23 while (n>0) { 24 if (n&1) res *= d; 25 d *= d; 26 n >>= 1; 27 } 28 return res; 29 } 30 31 vector<pair<int, int> > G[MAXN]; 32 int n, m; 33 34 void getGraph() { 35 for (int i = 0; i < MAXN; i++) 36 G[i].clear(); 37 n = 1; 38 for (int i = 30; i >= 0; i--) { 39 G[n].push_back(make_pair(n+1, 0)); 40 G[n].push_back(make_pair(n+2, (i!=0) ? (-myPow(2, i-1)) : 0)); 41 G[n+1].push_back(make_pair(n+2, -myPow(2, i))); 42 n += 2; 43 } 44 m = 0; 45 for (int i = 1; i <= n; i++) 46 m += G[i].size(); 47 } 48 49 void output() { 50 printf("%d %d\n", n, m); 51 for (int i = 1; i <= n; i++) 52 for (int j = 0; j < G[i].size(); j++) 53 printf("%d %d %d\n", i, G[i][j].first, G[i][j].second); 54 55 } 56 57 int main() { 58 #ifdef Phantom01 59 freopen("HDU4889.txt", "r", stdin); 60 #endif //Phantom01 61 62 getGraph(); 63 int C; 64 while (scanf("%d", &C)!=EOF) { 65 output(); 66 } 67 68 return 0; 69 } View Code

?

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

總結(jié)

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

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