题意

T组样例，N个地点，每个地点有个繁忙度，地点间有M条街道，每条街道要收过路费(目的地繁忙度-起点繁忙度)^3 （3次方），有Q个查询，包含Q个目的地，求从起点1到每个目的地的最小花费。如果花费小于3或者无法到达目的地，则输出"?"

解题思路

由于目的地繁忙度不一定大于起点繁忙度，所以图中有负环（一开始没想到，直接用dijkstra一直WA），所以要用bellman_ford来求最短路，当某些地点位于负环内，就肯定最终花费小于3。

AC代码

#include
    
     using namespace std;typedef long long ll;typedef pair
     
       pii;const int maxn = 1e3+5;const int maxm = 1e6+5;const int inf = 0x2f3f3f3f;         //这里给值小于初始dis数组赋值，原因可能是在跑bellman_ford的时候，负环和目的地的值相加变小了，直接判断目的地的值等于初始值的话，会waint N,M;int A[maxn];struct Edge {    int from,to,cost;};int dis[maxn];bool vis[maxn];Edge G[maxm];void bellman_ford(){    memset(dis,0x3f,sizeof(dis));    dis[1] = 0;    for(int i=1;i<=N;i++){        for(int j=0;j
      
       > T;    int Case = 1;    while(T--){        cin >> N;        for(int i=1;i<=N;i++){            cin >> A[i];        }        cin >> M;        int a,b;        Edge e;        memset(vis,0,sizeof(vis));        for(int i=0;i
       
        > a >> b;            e.from = a;            e.to = b;            e.cost = pow(A[b]-A[a],3);            G[i] = e;        }        int Q = 0;        cin >> Q;        cout << "Case " << Case++ << ":" << endl;        bellman_ford();        for(int i=0;i
        
         > t;            if(dis[t] < 3 || dis[t]>=inf || vis[t]){                cout << "?" << endl;            }else{                cout << dis[t] << endl;            }        }    }        return 0;}