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