d908: 4. 最佳路徑

#include <bits/stdc++.h>

using namespace std;

int n;

int d[101][101];

int main(){

   char c;int i, j;

   while(cin>>c>>n){

      int w,m=0;

      char a ,b;

      memset(d,0,sizeof(d));

        for (i = 0; i < n; ++i) {

            cin>>a>>b>>w;

            if(w > d[a-'A'][b-'A']) d[a-'A'][b-'A']=w;

        }

        for (int k = 0; k < n; ++k) {

            for (int i = 0; i < n; ++i)

                for (int j = 0; j < n; ++j)

                    if ((d[i][k] * d[k][j] != 0) && (i != j))

                            d[i][j] = max(d[i][j], d[i][k] + d[k][j]);

        }

        for (j = 0; j < n; ++j)  m=max(m,d[c-'A'][j]);

        cout<<m<<endl;

   }

   return 0;

}