一道简单的差分约束方程，差分约束方程由Bellmanford转换而来，一组差分方程由 x-y <=d 的形式，而在最短路中松弛条件有dis(x)<= dis(y)+w。 所以产生了一条由y连向x的有向边，权重为d。
1:
2: #include <queue>
3: #include <iostream>
4: #include <string.h>
5: #include <stdio.h>
6: using namespace std;
7: #define MAXN 1005 // vertex
8: #define MAXM 20005 // edge
9: #define INF 0x3F3F3F3F
10:
11: struct node
12: {
13: int v, w, next;
14: }pnt[MAXM];
15:
16: int head[MAXN];
17: int dis[MAXN];
18: bool vis[MAXN];
19: int cnt[MAXN]; // the number of the operation of push to Quque. negatvie cycle.
20: int num = 0; // the index of the edge
21: int N ; // the number of the vertex.
22: int M ; // the number of edges
23: int src, sink;
24: void addedge(int u, int v, int w)
25: {
26: pnt[num].v = v; pnt[num].w= w;
27: pnt[num].next = head[u]; head[u] = num++;
28: }
29:
30: int SPFA()
31: {
32: for(int i=0; i<=N; i++)
33: {
34: vis[i]=0; dis[i] = INF; cnt[i] = 0;
35: }
36:
37: queue<int> Q;
38: Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src];
39: while(!Q.empty())
40: {
41: int u = Q.front(); Q.pop(); vis[u] = 0;
42: for(int i=head[u]; i!=-1; i=pnt[i].next)
43: {
44: int v = pnt[i].v;
45: if( dis[v] > dis[u] + pnt[i].w )
46: {
47: dis[v] = dis[u] + pnt[i].w;
48: if(!vis[v]) {Q.push(v); vis[v] = 1;}
49: if( ++cnt[v] > N) return -1; // negative cycle.
50: }
51: }
52: }
53: if(dis[sink] == INF) return -2; // can't from src to sink.
54: return dis[sink];
55: }
56:
57: int main()
58: {
59: int ml,md;
60: while(scanf("%d%d%d", &N , &ml, &md)!= EOF)
61: {
62: num = 0;
63: memset(head, -1, sizeof(head));
64: int a, b, c;
65: for(int i=0; i<ml; i++)
66: {
67: scanf("%d%d%d", &a, &b, &c);
68: if(a>b) swap(a,b);
69: addedge(a, b,c);
70: }
71: for(int i=0; i<md; i++)
72: {
73: scanf("%d%d%d", &a, &b, &c);
74: if(a<b) swap(a,b);
75: addedge(a, b, -c);
76: }
77: src = 1; sink = N;
78: printf("%d\n", SPFA());
79: }
80: return 0;
81: }
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }