#1270321

Solution for 0304: School Cafeteria by tozangezan

Source Code Status Test Cases
    Policy: public     Reviewed: 169    
00.00 sec    1068 KB    76 lines     1935 bytes    2015-04-03 00:03
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
char in[210];
int A[210];
int O[210];
int B[210];
int S[210];
int D[210];
vector<int>as;
vector<pair<pair<int,int>,int> >edge;
int dist[210];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%s",in);
		int at=0;
		while('0'<=in[at]&&in[at]<='9'){
			A[i]*=10;A[i]+=in[at++]-'0';
		}
		A[i]--;
		if(in[at]=='<'){O[i]=1;at+=2;}
		else if(in[at]=='>'){O[i]=2;at+=2;}
		else {at++;as.push_back(i);}
		while('0'<=in[at]&&in[at]<='9'){
			B[i]*=10;B[i]+=in[at++]-'0';
		}
		B[i]--;
		if(in[at]=='+')S[i]=1;
		at++;
		while('0'<=in[at]&&in[at]<='9'){
			D[i]*=10;D[i]+=in[at++]-'0';
		}
	}
	int ret=-1;
	for(int i=0;i<(1<<(as.size()));i++){
		for(int j=0;j<as.size();j++){
			if(i&(1<<j))O[as[j]]=1;
			else O[as[j]]=2;
		}
		edge.clear();
		for(int j=0;j<b;j++){
			if(O[j]==1&&S[j]==1)edge.push_back(make_pair(make_pair(B[j],A[j]),-D[j]));
			if(O[j]==1&&S[j]==0){
				edge.push_back(make_pair(make_pair(A[j],B[j]),D[j]));
				edge.push_back(make_pair(make_pair(B[j],A[j]),0));
			}
			if(O[j]==2&&S[j]==1)edge.push_back(make_pair(make_pair(A[j],B[j]),-D[j]));
			if(O[j]==2&&S[j]==0){
				edge.push_back(make_pair(make_pair(B[j],A[j]),D[j]));
				edge.push_back(make_pair(make_pair(A[j],B[j]),0));
			}
		}
		for(int j=1;j<a;j++)edge.push_back(make_pair(make_pair(j,0),0));
	//	for(int j=0;j<edge.size();j++)printf("%d -> %d: %d\n",edge[j].first.first,edge[j].first.second,edge[j].second);
		for(int j=0;j<a;j++)dist[j]=999999999;
		dist[0]=0;
		int lastupd=-1;
		for(int j=0;j<a;j++){
			for(int k=0;k<edge.size();k++){
				if(dist[edge[k].first.second]>dist[edge[k].first.first]+edge[k].second){
					lastupd=j;
					dist[edge[k].first.second]=dist[edge[k].first.first]+edge[k].second;
				}
			}
		}
		if(lastupd!=a-1){
			for(int j=0;j<a;j++)ret=max(ret,dist[j]);
		}
	}
	if(ret>99999999)printf("inf\n");
	else printf("%d\n",ret);
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 22/22 C++ CPU: 00.00 sec Memory: 1068 KB Length: 1935 B 2015-04-03 00:03 2015-04-03 00:03
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 1036 KB
Case #2: : Accepted 00.00 sec 1032 KB
Case #3: : Accepted 00.00 sec 1020 KB
Case #4: : Accepted 00.00 sec 1036 KB
Case #5: : Accepted 00.00 sec 1036 KB
Case #6: : Accepted 00.00 sec 1036 KB
Case #7: : Accepted 00.00 sec 1036 KB
Case #8: : Accepted 00.00 sec 1036 KB
Case #9: : Accepted 00.00 sec 1032 KB
Case #10: : Accepted 00.00 sec 1028 KB
Case #11: : Accepted 00.00 sec 1052 KB
Case #12: : Accepted 00.00 sec 1040 KB
Case #13: : Accepted 00.00 sec 1056 KB
Case #14: : Accepted 00.00 sec 1060 KB
Case #15: : Accepted 00.00 sec 1056 KB
Case #16: : Accepted 00.00 sec 1056 KB
Case #17: : Accepted 00.00 sec 1036 KB
Case #18: : Accepted 00.00 sec 1028 KB
Case #19: : Accepted 00.00 sec 1044 KB
Case #20: : Accepted 00.00 sec 1068 KB
Case #21: : Accepted 00.00 sec 1068 KB
Case #22: : Accepted 00.00 sec 1068 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags