Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1A了,水题~差分系统+Bellman Ford,0ms无鸭梨

Posted by KatrineYang at 2016-09-16 13:23:53 on Problem 1364 and last updated at 2016-09-16 13:24:02
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator