| ||||||||||
| 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 | |||||||||
发一水代码!!!!#include <queue>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define inf 0x7FFFFFFF
#define M 110
using namespace std;
int end[M*M],edge_num,start[M*M],cost[M*M],next[M*M];
inline void Init(){
edge_num=0; memset(start,-1,sizeof(start));
}
void add_edge(int u,int v,int w){
end[edge_num]=v; cost[edge_num]=w; next[edge_num]=start[u]; start[u]=edge_num++;
}
int vis[M*9],d[M*9],cnt[M*9];
int spfa (int st,int n){
memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt));
for(int i=0;i<=n+5;i++) d[i]=-inf;
queue<int> Q; Q.push(st); cnt[st]++; d[st]=0;
vis[st]=1; int u,v,w;
while(!Q.empty()){
u=Q.front(),Q.pop(),vis[u]=0;
for(int i=start[u];i!=-1;i=next[i]){
v=end[i],w=cost[i];
if(d[v]<d[u]+w){
d[v]=d[u]+w;
if(!vis[v]){
vis[v]=1,Q.push(v);
if(++cnt[v]>n+1) return 0;
}
}
}
}
return 1;
}
int main(){
int n,m,u,v,w;
char s[8];
while(~scanf("%d",&n),n,cin>>m){
cin>>m; Init();
while(m--){
scanf("%d%d %s %d",&u,&v,s,&w);
if(s[0]=='g') add_edge(u-1,u+v,w+1);
else add_edge(u+v,u-1,1-w);
}
for(int i=0;i<=n;i++) add_edge(n+7,i,0);
if(spfa(n+7,n)) puts("lamentable kingdom");
else puts("successful conspiracy");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator