最短spfa+dijstraスタック最適化の復習

     ，，   wa   ，，         clear（）。。。
     spfa     bell_forman                            （             ）             （    ）
   vis                                  vis     
              
                  ，           。                 ，         “     ”   ，        ，      。
  ，               ，    ，          （  d[]           ，          ，         ），  “  ” 
                   。                ，  “    ”    。          ？
       Bellman-Ford  ，       ？  ，    Bellman-Ford              ，     |V|-1     。         ，SPFA  
“     ”，         ，   SPFA ，       ——         ——   |V| ，                。（http://www.cnblogs.com/jiangu66/p/3235361.html）


23     ~
void spfa(int s)
{
    int vis[V];
    int d[V],ret[V];
    for(int i=1;i<=n;i++) d[i]=inf,vis[i]=ret[i]=0;
    d[s]=0;
    queue<int> q;
    q.push(s);
    ret[s]++;
    vis[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=0;i<fuck[now].size();i++)
        {
            node temp=fuck[now][i];
            if(d[temp.point]>d[now]+temp.cost)
            {
                d[temp.point]=d[now]+temp.cost;
                if(vis[temp.point]==0)
                {
                    vis[temp.point]=1;
                    ret[temp.point]++;
                    q.push(temp.point);
                    if(ret[temp.point]>V)
                    {
                        cout<1<<endl;
                        return ;
                    }
                }
            }
        }

    }
    cout<<d[n]<<endl;
}
int main()
{
   while(cin>>n>>m)
   {
       if(n==0&&m==0) break;
       for(int i=1;i<=n;i++) fuck[i].clear();
       for(int i=1;i<=m;i++)
       {
           int x,y,cost;
           cin>>x>>y>>cost;
           node temp;
           temp.cost=cost;
           temp.point=x;
           fuck[y].push_back(temp);
           temp.point=y;
           fuck[x].push_back(temp);
       }
      dijstra(1);
      //spfa(1);
   }
   return 0;
}