- 1#include 2#include 3#include 4 using namespace std;
- 5 const int maxn = 1010;
- 6 const int maxe = 20010;
- 7 const int inf = 0x3f3f3f3f;
- 8 int n,
- m,
- c;
- 9 int u,
- v,
- w;
- 10 struct edge 11 {
- 12 int v,
- w,
- nex;
- 13
- }
- e[maxe];
- 14 int head[maxn],
- ins[maxn],
- sta[maxn],
- dis[maxn];
- 15 int cnt;
- 16 17 void add(int u, int v, int w) 18 {
- 19 e[cnt].v = v;
- 20 e[cnt].w = w;
- 21 e[cnt].nex = head[u];
- 22 head[u] = cnt++;
- 23
- }
- 24 25 int spfa(int s) 26 {
- 27
- for (int i = 1; i <= n; i++) 28 {
- 29 dis[i] = inf;
- 30 ins[i] = 0;
- 31
- }
- 32 dis[s] = 0;
- 33 ins[s] = 1;
- 34 int top = 0;
- 35 sta[top++] = s;
- 36
- while (top) 37 {
- 38 int u = sta[--top];
- 39
- for (int i = head[u]; i != -1; i = e[i].nex) 40 {
- 41 int v = e[i].v;
- 42 int w = e[i].w;
- 43
- if (ins[v] == n) return - 1; //入队>=n次;说明存在负环
- 44
- if (dis[v] > dis[u] + w) 45 {
- 46 dis[v] = dis[u] + w;
- 47 ins[v]++;
- 48 sta[top++] = v;
- 49
- }
- 50
- }
- 51
- }
- 52
- if (dis[n] == inf) return - 2; //说明不可达
- 53
- else return dis[n];
- 54
- }
- 55 56 int main() 57 {
- 58
- while (scanf("%d%d%d", &n, &m, &c) != EOF) 59 {
- 60 memset(head, -1, sizeof head);
- 61 cnt = 0;
- 62
- for (int i = 0; i) 63 {
- 64 scanf("%d%d%d", &u, &v, &w); //d[v]-d[u]<=w -> d[v]<=d[u]+w -> if: d[v]>d[u]+w
- 65
- if (u > v) swap(u, v);
- 66 add(u, v, w);
- 67
- }
- 68
- for (int i = 0; i) 69 {
- 70 scanf("%d%d%d", &u, &v, &w); // d[v]-d[u]>=w -> d[u]<=d[v]-w -> if: d[u]>d[v]-w
- 71
- if (u > v) swap(u, v);
- 72 add(v, u, -w);
- 73 74
- }
- 75 printf("%d\n", spfa(1));
- 76 77 78
- }
- 79
- return 0;
- 80
- }
来源: http://www.bubuko.com/infodetail-1995316.html