| ||||||||||
| 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 | |||||||||
1A了,水题~差分系统+Bellman Ford,0ms无鸭梨#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main() {
while(1){
int n,m;
scanf("%d", &n);
if(!n) break;
scanf("%d", &m);
int adjNo[110] = {0};
int adjList[110][110];
int weight[110][110];
for(int ii = 0; ii < m; ii++){
int i,j,k;
char s[4];
scanf("%d%d%s%d", &i, &j, s, &k);
if(strcmp(s, "gt") == 0){
adjList[i+j][adjNo[i+j]] = i-1;
weight[i+j][adjNo[i+j]] = -k-1;
adjNo[i+j]++;
}
else{
adjList[i-1][adjNo[i-1]] = i+j;
weight[i-1][adjNo[i-1]] = k-1;
adjNo[i-1]++;
}
}
int dist[110] = {0};
for(int ii = 0; ii < n; ii++){
for(int i = 0; i <= n; i++){
for(int j = 0; j < adjNo[i]; j++){
if(dist[adjList[i][j]] > dist[i] + weight[i][j]){
dist[adjList[i][j]] = dist[i] + weight[i][j];
}
}
}
}
bool ky = 1;
for(int i = 0; i <= n; i++){
for(int j = 0; j < adjNo[i]; j++){
if(dist[adjList[i][j]] > dist[i] + weight[i][j]){
ky = 0;
goto done;
}
}
}
done:
if(ky){
printf("lamentable kingdom\n");
}
else{
printf("successful conspiracy\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator