题目链接：
http://lightoj.com/volume_showproblem.php?problem=1074
题目大意：
有一个大城市有n个十字交叉口，有m条路，城市十分拥挤，因此每一个路都有一个拥挤度，*就出台了一个政策，对每一条路收取过路费，收取标准为（终点拥挤度 - 起点拥挤度 ）3,，问每次询问m，输出1到m的最小花费，如果不能到达或者最小化费小于3的时候输出‘？’。
解题思路：
用spfa。标记负环。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; #define maxn 210
#define INF 0x3f3f3f3f struct Edge
{
int e, w;
Edge(int e=, int w=):e(e),w(w){}
}; vector<Edge>G[maxn];
int dist[maxn], n;
bool Cin[maxn];
void init();
int spfa ();
void dfs (int u); int main ()
{
int m, t, l=, map[maxn];
scanf ("%d", &t); while (t --)
{
printf ("Case %d:\n", ++l);
init ();
scanf ("%d", &n); for (int i=; i<=n; i++)
scanf ("%d", &map[i]); scanf ("%d", &m);
while (m --)
{
int a, b, num;
scanf ("%d %d", &b, &a);
num = (map[a] - map[b]) * (map[a] - map[b]) * (map[a] - map[b]);
G[b].push_back (Edge(a, num));
}
spfa ();
scanf ("%d", &m);
while (m --)
{
int num;
scanf ("%d", &num);
if (Cin[num] || dist[num] < || dist[num] == INF)
printf ("?\n");
else
printf ("%d\n", dist[num]);
}
}
}
void init()
{
int i, j;
memset (Cin, false, sizeof(Cin));
for (i=; i<maxn; i++)
{
G[i].clear();
dist[i] = INF;
}
} int spfa ()
{
queue<int>Q;
bool vis[maxn];
int cnt[maxn];
memset (vis, false, sizeof(vis));
memset (cnt, , sizeof(cnt));
Q.push ();
cnt[] = ;
dist[] = ; while (!Q.empty())
{
int s = Q.front ();
Q.pop ();
vis[s] = false;
int len = G[s].size(); for (int i=; i<len; i++)
{
Edge x = G[s][i];
if (Cin[x.e])
continue;
if (dist[x.e] > dist[s] + x.w)
{
dist[x.e] = dist[s] + x.w;
if (!vis[x.e])
{
vis[x.e] = true;
Q.push (x.e);
cnt[x.e] ++;
if (cnt[x.e] == n)//只要x.e在负环内，则在负环内的点可以到达的点，都没有最短路径
dfs(x.e);
}
}
}
}
} void dfs (int u)
{
int len = G[u].size();
Cin[u] = true;
for (int i=; i<len; i++)//u后面的点都没有最短回路，都应该标记 {
if (!Cin[G[u][i].e])
dfs (G[u][i].e);
}
}