题目链接：

　　

题目大意：

　　有一个大城市有n个十字交叉口，有m条路，城市十分拥挤，因此每一个路都有一个拥挤度，政府就出台了一个政策，对每一条路收取过路费，收取标准为（终点拥挤度 - 起点拥挤度 ）^3,，问每次询问m，输出1到m的最小花费，如果不能到达或者最小化费小于3的时候输出‘？’。

解题思路：

　　用spfa。标记负环。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 using namespace std; 9 10 #define maxn 210 11 #define INF 0x3f3f3f3f 12 13 struct Edge 14 { 15 int e, w; 16 Edge(int e=0, int w=0):e(e),w(w){} 17 }; 18 19 vector
            
             G[maxn]; 20 int dist[maxn], n; 21 bool Cin[maxn]; 22 void init(); 23 int spfa (); 24 void dfs (int u); 25 26 int main () 27 { 28 int m, t, l=0, map[maxn]; 29 scanf ("%d", &t); 30 31 while (t --) 32 { 33 printf ("Case %d:\n", ++l); 34 init (); 35 scanf ("%d", &n); 36 37 for (int i=1; i<=n; i++) 38 scanf ("%d", &map[i]); 39 40 scanf ("%d", &m); 41 while (m --) 42 { 43 int a, b, num; 44 scanf ("%d %d", &b, &a); 45 num = (map[a] - map[b]) * (map[a] - map[b]) * (map[a] - map[b]); 46 G[b].push_back (Edge(a, num)); 47 } 48 spfa (); 49 scanf ("%d", &m); 50 while (m --) 51 { 52 int num; 53 scanf ("%d", &num); 54 if (Cin[num] || dist[num] < 3 || dist[num] == INF) 55 printf ("?\n"); 56 else 57 printf ("%d\n", dist[num]); 58 } 59 } 60 } 61 void init() 62 { 63 int i, j; 64 memset (Cin, false, sizeof(Cin)); 65 for (i=0; i
             

Q; 75 bool vis[maxn]; 76 int cnt[maxn]; 77 memset (vis, false, sizeof(vis)); 78 memset (cnt, 0, sizeof(cnt)); 79 Q.push (1); 80 cnt[1] = 1; 81 dist[1] = 0; 82 83 while (!Q.empty()) 84 { 85 int s = Q.front (); 86 Q.pop (); 87 vis[s] = false; 88 int len = G[s].size(); 89 90 for (int i=0; i

dist[s] + x.w) 96 { 97 dist[x.e] = dist[s] + x.w; 98 if (!vis[x.e]) 99 {100 vis[x.e] = true;101 Q.push (x.e);102 cnt[x.e] ++;103 if (cnt[x.e] == n)//只要x.e在负环内，则在负环内的点可以到达的点，都没有最短路径104 dfs(x.e);105 }106 }107 }108 }109 }110 111 void dfs (int u)112 {113 int len = G[u].size();114 Cin[u] = true;115 for (int i=0; i