【POJ】3268 Silver Cow Party

题意：有N头奶牛，M条单向路。X奶牛开party，其他奶牛要去它那里。每头奶牛去完X那里还要返回。去回都是走的最短路。现在问这里面哪头奶牛走的路最长。

题解：对每个奶牛i与X做两次spfa。去回各一次。然后统计最长的。。板子稍微改一改//但是我还是T了好几发，因为初始化数组的时候maxn开大了。。QAQ。改小了就过了。

代码：

 #include<iostream>

 #include<stack>

 #include<vector>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

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

 int n,m,X;

 int d[maxn],inq[maxn];

 int spfa(int s,int t){

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

         inq[i] = ;

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

         d[i] = 1e9;

     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);

             }

         }

     }

     return d[t];

 }

 int main() {

     scanf("%d%d%d",&n,&m,&X);

     int x,y,z;

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

         scanf("%d%d%d",&x,&y,&z);

         //cin>>x>>y>>z;

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

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

     }

     int ans = ;

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

         if(i == X){

             continue;

         }

         int sum = spfa(X,i);

         sum += spfa(i,X);

         ans = max(ans,sum);

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

【POJ】3268 Silver Cow Party

最新文章

热门文章