d908. 4. 最佳路徑 -- 99學年度北基區資訊學科能力競賽 | From: [1.175.132.48] | 發表日期 : 2017-11-19 20:21

#include<bits/stdc++.h>
using namespace std;

 

queue <int> q;

 

int main(int argc, char** argv) {
 char star , a , b; bool if_[26];
 int n , d[26][26] , len;
 while(~scanf("%c",&star)) {
        while(star=='\n'||star==' ') scanf("%c",&star);
  memset(d,-1,sizeof(d)); memset(if_,0,26);
  scanf("%d",&n); getchar();
  for(int i=0;i<n;i++) {
   scanf("%c %c %d",&a,&b,&len); getchar();
   if(len>d[a-'A'][b-'A']) d[a-'A'][b-'A']=len;
  }
  q.push(star-'A'); d[star-'A'][star-'A']=0;
  int ans=0;
  while(q.empty()==0) {
   int now=q.front(); q.pop();
   for(int i=0;i<26;i++) if(d[now][i]>0) {
    d[star-'A'][i]=max(d[now][i]+d[star-'A'][now],d[star-'A'][i]);
    ans=max(d[star-'A'][i],ans);
    if(if_[i]==0) q.push(i); if_[i]=1;
   }
  }
  if(ans>0) printf("%d\n",ans);
 }
 return 0;
}

 

#0: 20% AC (0ms, 296KB)