## #1270321

Solution for 0304: School Cafeteria by tozangezan

Source Code Status Test Cases
Policy: public     Reviewed: 198
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 #  ( | )