poj 2983Is the Information Reliable?

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxm 5000100
 5 #define maxn 3010
 6 using namespace std;
 7 int head[maxn],next[maxn],dis[maxn];
 8 bool vis[maxn];
 9 int e,n,m;
10 const int inf=1<<23;
11 struct node
12 {
13     int u,v,c;
14     node(){}
15     node(int u,int v,int c):u(u),v(v),c(c){}
16 }p[maxm];
17 
18 void addnode(int u,int v,int c)
19 {
20     p[e]=node(u,v,c);
21     next[e]=head[u];head[u]=e++;
22 }
23 
24 void inti()
25 {
26     memset(head,-1,sizeof(head));
27     memset(next,-1,sizeof(next));
28     e=0;
29     for(int i=0; i<m; i++)
30     {
31         char ch;int u,v,c;
32         scanf("%c",&ch);
33         if(ch=='P')
34         {
35             scanf("%d%d%d",&u,&v,&c);
36             getchar();
37             addnode(u,v,-c);
38             addnode(v,u,c);
39         }
40         else if(ch=='V')
41         {
42             scanf("%d%d",&u,&v);
43             getchar();
44             addnode(u,v,-1);
45         }
46     }
47 }
48 
49 void  Bellman_ford()
50 {
51     bool flag;
52     for(int i=0; i<=n; i++) dis[i]=inf;
53     for(int i=1; i<=n; i++)
54     {
55         flag=true;
56         for(int j=0; j<e; j++)
57         {
58             if(dis[p[j].v]>dis[p[j].u]+p[j].c)
59             {
60                 dis[p[j].v]=dis[p[j].u]+p[j].c;
61                 flag=false;
62             }
63         }
64         if(flag) break;
65     }
66     if(!flag) printf("Unreliable
");
67     else printf("Reliable
");
68 }
69 
70 int main()
71 {
72     while(scanf("%d%d",&n,&m)!=EOF)
73     {
74         getchar();
75         inti();
76         Bellman_ford();
77     }
78     return 0;
79 }

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxm 500010
 5 #define maxn 3010
 6 using namespace std;
 7 int head[maxn],next[maxn],dis[maxn];
 8 bool vis[maxn];
 9 int e,n,m;
10 const int inf=1<<30;
11 struct node
12 {
13     int u,v,c;
14     node(){}
15     node(int u,int v,int c):u(u),v(v),c(c){}
16 }p[maxm];
17 
18 void addnode(int u,int v,int c)
19 {
20     p[e]=node(u,v,c);
21     next[e]=head[u];head[u]=e++;
22 }
23 
24 void inti()
25 {
26     memset(head,-1,sizeof(head));
27     memset(next,-1,sizeof(next));
28     e=0;
29     for(int i=0; i<m; i++)
30     {
31         char ch;
32         int u,v,c;
33         scanf("%c",&ch);
34         if(ch=='P')
35         {
36             scanf("%d%d%d",&u,&v,&c);
37             getchar();
38             addnode(u,v,-c);
39             addnode(v,u,c);
40         }
41         else if(ch=='V')
42         {
43             scanf("%d%d",&u,&v);
44             getchar();
45             addnode(u,v,-1);
46         }
47     }
48 }
49 
50 void  Bellman_ford()
51 {
52     bool flag;
53     for(int i=0; i<=n; i++) dis[i]=inf;
54     for(int i=1; i<=n; i++)
55     {
56         for(int j=0; j<e; j++)
57         {
58             if(dis[p[j].v]>dis[p[j].u]+p[j].c)
59             {
60                 dis[p[j].v]=dis[p[j].u]+p[j].c;
61             }
62         }
63     }
64     flag=true;
65     for(int j=0; j<e; j++)
66     {
67         if(dis[p[j].v]>dis[p[j].u]+p[j].c)
68         {
69             flag=false;
70             break;
71         }
72     }
73     if(!flag) printf("Unreliable
");
74     else printf("Reliable
");
75 }
76 
77 int main()
78 {
79     while(scanf("%d%d",&n,&m)!=EOF)
80     {
81         getchar();
82         inti();
83         Bellman_ford();
84     }
85     return 0;
86 }

View Code