记录一下这种题型，以防忘记。
题意：给出n个城市，每个城市都有一个拥挤度，从a到b的时间是（b的拥挤度-a的拥挤度）^3，点1为起点，求最短时间。 最后判断条件只要是最短路小于3或等于inf或位于负环上都输出问号，其他情况输出最小值即可。
如果有负环，遍历会超过n-1次
这题不适合邻接矩阵来做，可以用链式前向星存储，也可以直接用vector< edge >存储。
#include <bits/stdc++.h> #pragma GCC optimize(2) using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int maxn=200+7; int n,m,a[maxn][maxn],T,x,y,o; struct edge{ int to,w; edge(int a,int b){ to=a; w=b; } }; vector<edge>sz[maxn]; int d[maxn],cnt[maxn],b[maxn]; bool vis[maxn]; int dis(int i,int j){ return (b[j]-b[i])*(b[j]-b[i])*(b[j]-b[i]); } void spfa(){ memset(d,inf,sizeof(d)); memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); d[1]=0; vis[1]=1; cnt[1]++; queue<int>q; q.push(1); while(!q.empty()){ int t=q.front(); q.pop(); vis[t]=0; for(int i=0;i<sz[t].size();i++){ y=sz[t][i].to; x=sz[t][i].w; if(d[y]>x+d[t]){ d[y]=x+d[t]; if(!vis[y]&&cnt[y]<=n-1){ //注意判断 vis[y]=1; q.push(y); cnt[y]++; //区别点 } } } } } int main(){ cin>>T; while(T--){ cin>>n; for(int i=1;i<=n;i++){ sz[i].clear(); cin>>b[i]; } cin>>m; for(int i=1;i<=m;i++){ cin>>x>>y; sz[x].push_back(edge(y,dis(x,y))); } spfa(); int tt; cin>>tt; o++; cout<<"Case "<<o<<":"<<endl; while(tt--){ cin>>x; if(d[x]<3||d[x]==inf||cnt[x]>=n-1) cout<<"?"<<endl; else cout<<d[x]<<endl; } } }