Source Code

Problem: 1135  User: yzhw 
Memory: 728K  Time: 0MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
# include <vector>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <queue>
using namespace std;
int n,m;
struct node
{
   int t,p;
};
vector<node> data[501];
int len[501];
class cmp
{
   public:
      bool operator()(const int a,const int b) const
      {
         return len[a]>len[b];
      }
};
void caldis()
{
   bool used[501];
   for(int i=1;i<=n;i++)
     len[i]=9999999;
   memset(used,0,sizeof(used));
   len[1]=0;
   priority_queue<int,vector<int>,cmp> q;
   q.push(1);
   while(!q.empty())
   {
       int pos=q.top();
       q.pop();
       used[pos]=1;
       for(int i=0;i<data[pos].size();i++)
         if(!used[data[pos][i].t]&&len[data[pos][i].t]>len[pos]+data[pos][i].p)
             {
                len[data[pos][i].t]=len[pos]+data[pos][i].p;
                q.push(data[pos][i].t);
             }
   }
}
int main()
{
    int tc=1;
    while(true)
    {
       cin>>n>>m;
       if(!n&&!m) break;
       for(int i=1;i<=n;i++)
         data[i].clear();
       for(int i=1;i<=m;i++)
       {
           int f,t;
           node tmp;
           cin>>f>>t>>tmp.p;
           tmp.t=t;
           data[f].push_back(tmp);
           tmp.t=f;
           data[t].push_back(tmp);
       }
       caldis();
       int ans=1,a1,a2;
       bool flag=false;
       double maxnum=0;
       for(int i=1;i<=n;i++)
        if(len[i]>maxnum)
           maxnum=len[i],ans=i;
       for(int i=1;i<=n;i++)
         for(int j=0;j<data[i].size();j++)
           if(abs(len[i]-len[data[i][j].t])<data[i][j].p)
           {
              double total=0;
              int d=abs(len[i]-len[data[i][j].t]);
              total=min(len[i],len[data[i][j].t])+d+(data[i][j].p-d)/2.0;
              if(total>maxnum)
              {
                 maxnum=total;
                 flag=true;
                 a1=min(i,data[i][j].t);
                 a2=max(i,data[i][j].t);
              }
           }
       printf("System #%d\n",tc++);
       if(flag)
         printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n",maxnum,a1,a2);
       else
         printf("The last domino falls after %.1f seconds, at key domino %d.\n\n",maxnum,ans);
    }
    return 0;
}