題目很好理解，轉換為差分約束也好理解。
關鍵是差分約束是要n+1個點，多一個v0，但是如果按照差分去做，肯定會wa，因為這樣做以後，樣例肯定都過不了，想想看，v0到其他點距離為0，所以到v1最短為0，v4最短為0，怎麼求都得不到最後的27啊？？？？？
還有像vj>=vi(j >= i)這些約束不用加，這個好理解，證明題目中沒給這一塊的測試用例，數據弱沒關系，但是如果你加上了，可能會報錯。
discuss好多疑問，，但是無人解決，只能說這題目還是有爭議的。
一個解釋：
差分約束系統有兩種方式可以求解，最短路和最長路。當我們把不等式整理成d[a]+w<=d[b]時，我們求最長路。整理成d[a]+w>=d[b]時，我們求最短路。當求最短路時，我們通常要把各點距離初始化為正無窮，求最短路，把各點距離逐漸減小，直到符合所有不等式。也就是開始各點不符合條件，後來通過減小變得符合了，所以一定是符合條件的最大值。既然是求最大值，並且是減小各點距離，也就是把各點由數軸的右側向左側拉，所以我們一定要選擇一個最終在數軸最左側的點，並初始化為0，把所有正無窮的點拉近到符合不等式。最長路同理。
一肚子疑問，雖然如此，但是還是對差分約束有了了解，就是給出一些不等式類似xj-xi<=wb 這樣的，能夠通過求最短路獲得其中的一組解，這也是數學計算機化的一種表現吧。
無語。。。。。忘牛人指示，下面是沒有按照差分約束概念做的，a了，但是感覺好不爽，疑問很多。。。
[cpp]
#include <stdio.h>
#define maxN 1100
#define inf 1000000000
struct EDGE
{
int v, w, next;
}edge[20 * maxN];
int preEdge[maxN];
int dis[maxN];
int edgeNum;
bool vis[maxN];
int queue[20 * maxN];
int cnt[maxN];
int N;
void Init()
{
for (int i = 1; i <= N; ++ i)
{
dis[i] = inf;
vis[i] = false;
preEdge[i] = 0;
cnt[i] = 0;
}
}
bool spfa()
{
int head = 0, tail = 1;
queue[0] = 1;
dis[1] = 0;
while (head < tail)
{
int u = queue[head];
vis[u] = true;
int p = preEdge[u];
while (p != 0)
{
int v = edge[p].v;
int w = edge[p].w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if (!vis[v])
{
vis[v] = true;
queue[tail] = v;
tail ++;
}
if (++ cnt[v] > N)
{
return false;
}
}
p = edge[p].next;
}
vis[u] = false;
head ++;
}
return true;
}
void addEdge(int u, int v, int w)
{
edge[edgeNum].v = v;
edge[edgeNum].w = w;
edge[edgeNum].next = preEdge[u];
preEdge[u] = edgeNum ++;
//edgeNum ++;
}
int main()
{
int ML, MD;
while (scanf("%d%d%d", &N, &ML, &MD) != EOF)
{
edgeNum = 1;
int u, v, w;
Init();
for (int i = 0; i < ML; ++ i)
{
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
}
for (int i = 0; i < MD; ++ i)
{
scanf("%d%d%d", &u, &v, &w);
addEdge(v, u, -w);
}
//for (int i = 2; i <= N; ++ i)
//{
// addEdge(i, 1, 0);
// addEdge(i,i - 1, 0);
//}
if(!spfa())
printf("-1\n");
else if (dis[N] == inf)
{
printf("-2\n");
}
else
printf("%d\n", dis[N]);
}
return 0;
}
作者：zhang20072844
