| ||||||||||
| 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