Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
spfa希望对大家有帮助#include <iostream> #include <stdio.h> #include <queue> using namespace std; const int MAXN = 1000; const int MAXM = 100000; const int inf = 0x3fffffff; struct node { int to, next, w; }edge[MAXM*3]; int box[MAXN+10], ecnt; int dist[MAXN+10]; bool visit[MAXN+10]; int Count[MAXN+10]; int n, m; void make_map(int from, int to, int w) { edge[ecnt].to = to; edge[ecnt].w = w; edge[ecnt].next = box[from]; box[from] = ecnt++; } bool spfa() { queue<int>que; for(int i = 0; i <= n; i++) { visit[i] = false; dist[i] = inf; } dist[0] = 0; Count[0] = 1; que.push(0); visit[0] = true; while(!que.empty()) { int x = que.front(); que.pop(); visit[x] = false; for(int i = box[x]; i+1; i = edge[i].next) { int e = edge[i].to; if(dist[e] > dist[x]+edge[i].w) { dist[e] = dist[x]+edge[i].w; if(!visit[e]) { visit[e] = true; que.push(e); Count[e]++; if(Count[e] > n+1) return false; } } } } return true; } int main() { //freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m) != EOF) { memset(box, -1, sizeof(box)); memset(Count, 0, sizeof(Count)); ecnt = 0; char str[3]; for(int i = 1; i <= m; i++) { scanf("%s", str); if(str[0] == 'P') { int u, v, w; scanf("%d%d%d", &u, &v, &w); make_map(u, v, -w); make_map(v, u, w); } else { int u, v; scanf("%d%d", &u, &v); make_map(u, v, -1); } } for(int i = 1; i <= n; i++) make_map(0, i, 0); if(spfa()) puts("Reliable"); else puts("Unreliable"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator