【POJ】2387 Til the Cows Come Home

题意：求从1到n的最短路

题解：板子题。spfa。

代码：

 #include<iostream>

 #include<stack>

 #include<vector>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int maxn = 2e5+;

 vector< pair<int,int> > e[maxn];

 int n,m;

 int d[maxn],inq[maxn];

 void init(){

     for(int i = ; i < maxn; i++)

         e[i].clear();

     for(int i =  ;i < maxn ; i++)

         inq[i] = ;

     for(int i =  ; i < maxn ; i++)

         d[i] = 1e9;

 }

 int main(int argc, const char * argv[]) {

     while(cin>>m>>n){

         init();

         int x,y,z;

         for(int i = ; i < m ;i++){

             cin>>x>>y>>z;

             e[x].push_back(make_pair(y,z));

             e[y].push_back(make_pair(x,z));

         }

         int s,t;

         //cin>>s>>t;

         s = ;

         t = n;

         queue<int>Q;

         Q.push(s);d[s] =  ;inq[s] = ;

         while( !Q.empty() ){

             int now = Q.front();

             Q.pop();

             inq[now] = ;

             for(int i = ; i < e[now].size() ; i++){

                 int v = e[now][i].first;

                 if(d[v] > d[now] + e[now][i].second){

                     d[v] = d[now] + e[now][i].second;

                     if(inq[v] == )

                         continue;

                     inq[v] = ;

                     Q.push(v);

                 }

             }

         }

         if(d[t] == 1e9)

             cout<<-<<endl;

         else

             cout<<d[t]<<endl;

     }

     return ;

 }

看题没看仔细。。。一直n和m输入反了，还以为是去重的问题。搞了好久。。然后发现其实pair这样存储的模式不用考虑去重的问题。也算是有所收获吧。哎。心痛。。