http://acm.pku.edu.cn/JudgeOnline/problem?id=1364
先貼個(gè)代碼，差分約束，雖然參照別人放入代碼過(guò)了，但是自己也搞得不是太明白！
慢慢學(xué)習(xí)！
Source Code
| Problem: 1364 |
|
User: lovecanon |
| Memory: 208K |
|
Time: 0MS |
| Language: C++ |
|
Result: Accepted |
#include<iostream>
#include<string.h>
using namespace std;
struct node{
int u,v,val;
}edge[101];
int a,b,va,i,j,n,m,dist[101];
char rel[3];
void bellman_ford(){
memset(dist,0,sizeof(dist));
int flag;
for(i=0;i<=n;i++){
flag=0;
for(j=1;j<=m;j++){
if(dist[edge[j].u]+edge[j].val<dist[edge[j].v]){//can de updated
dist[edge[j].v]=dist[edge[j].u]+edge[j].val;
flag=1;
}
}
if(!flag) break;
}
if(!flag) printf("lamentable kingdom\n");
else printf("successful conspiracy\n");
}
int main(){
while(scanf("%d",&n)&&n){
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d%d%s%d",&a,&b,rel,&va);
if(rel[0]=='l'){
edge[i].u=a+b;
edge[i].v=a-1;//a-1 not b-1 在這兒錯(cuò)了好多次
edge[i].val=va-1;
}
else{
edge[i].u=a-1;
edge[i].v=a+b;
edge[i].val=-1-va;
}
}
bellman_ford();
}
return 0;
}