http://poj.org/problem?id=2983
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxm 5000100
#define maxn 3010
using namespace std;
int head[maxn],next[maxn],dis[maxn];
bool vis[maxn];
int e,n,m;
const int inf=<<;
struct node
{
int u,v,c;
node(){}
node(int u,int v,int c):u(u),v(v),c(c){}
}p[maxm]; void addnode(int u,int v,int c)
{
p[e]=node(u,v,c);
next[e]=head[u];head[u]=e++;
} void inti()
{
memset(head,-,sizeof(head));
memset(next,-,sizeof(next));
e=;
for(int i=; i<m; i++)
{
char ch;int u,v,c;
scanf("%c",&ch);
if(ch=='P')
{
scanf("%d%d%d",&u,&v,&c);
getchar();
addnode(u,v,-c);
addnode(v,u,c);
}
else if(ch=='V')
{
scanf("%d%d",&u,&v);
getchar();
addnode(u,v,-);
}
}
} void Bellman_ford()
{
bool flag;
for(int i=; i<=n; i++) dis[i]=inf;
for(int i=; i<=n; i++)
{
flag=true;
for(int j=; j<e; j++)
{
if(dis[p[j].v]>dis[p[j].u]+p[j].c)
{
dis[p[j].v]=dis[p[j].u]+p[j].c;
flag=false;
}
}
if(flag) break;
}
if(!flag) printf("Unreliable\n");
else printf("Reliable\n");
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
getchar();
inti();
Bellman_ford();
}
return ;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxm 500010
#define maxn 3010
using namespace std;
int head[maxn],next[maxn],dis[maxn];
bool vis[maxn];
int e,n,m;
const int inf=<<;
struct node
{
int u,v,c;
node(){}
node(int u,int v,int c):u(u),v(v),c(c){}
}p[maxm]; void addnode(int u,int v,int c)
{
p[e]=node(u,v,c);
next[e]=head[u];head[u]=e++;
} void inti()
{
memset(head,-,sizeof(head));
memset(next,-,sizeof(next));
e=;
for(int i=; i<m; i++)
{
char ch;
int u,v,c;
scanf("%c",&ch);
if(ch=='P')
{
scanf("%d%d%d",&u,&v,&c);
getchar();
addnode(u,v,-c);
addnode(v,u,c);
}
else if(ch=='V')
{
scanf("%d%d",&u,&v);
getchar();
addnode(u,v,-);
}
}
} void Bellman_ford()
{
bool flag;
for(int i=; i<=n; i++) dis[i]=inf;
for(int i=; i<=n; i++)
{
for(int j=; j<e; j++)
{
if(dis[p[j].v]>dis[p[j].u]+p[j].c)
{
dis[p[j].v]=dis[p[j].u]+p[j].c;
}
}
}
flag=true;
for(int j=; j<e; j++)
{
if(dis[p[j].v]>dis[p[j].u]+p[j].c)
{
flag=false;
break;
}
}
if(!flag) printf("Unreliable\n");
else printf("Reliable\n");
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
getchar();
inti();
Bellman_ford();
}
return ;
}