商城网站哪个公司做的好,网络推广专员,模板网站好还是定制网站好,济南建设信用网网站题目链接#xff1a;http://poj.org/problem?id3268 题意 #xff1a;有N头奶牛#xff0c;M条单向路。X奶牛开party#xff0c;其他奶牛要去它那里。每头奶牛去完X那里还要返回。去回都是走的最短路。现在问这里面哪头奶牛走的路最长。 题解#xff1a;对每个奶牛i与X做…题目链接http://poj.org/problem?id3268 题意 有N头奶牛M条单向路。X奶牛开party其他奶牛要去它那里。每头奶牛去完X那里还要返回。去回都是走的最短路。现在问这里面哪头奶牛走的路最长。 题解对每个奶牛i与X做两次spfa。去回各一次。然后统计最长的。。板子稍微改一改//但是我还是T了好几发因为初始化数组的时候maxn开大了。。QAQ。改小了就过了。 代码 1 #includeiostream2 #includestack3 #includevector4 #includequeue5 #includealgorithm6 using namespace std;7 const int maxn 100005;8 9 vector pairint,int e[maxn];
10
11 int n,m,X;
12 int d[maxn],inq[maxn];
13
14 int spfa(int s,int t){
15 for(int i 0 ;i maxn ; i)
16 inq[i] 0;
17 for(int i 0 ; i maxn ; i)
18 d[i] 1e9;
19 queueintQ;
20 Q.push(s);d[s] 0 ;inq[s] 1;
21 while( !Q.empty() ){
22 int now Q.front();
23 Q.pop();
24 inq[now] 0;
25 for(int i 0; i e[now].size() ; i){
26 int v e[now][i].first;
27 if(d[v] d[now] e[now][i].second){
28 d[v] d[now] e[now][i].second;
29 if(inq[v] 1)
30 continue;
31 inq[v] 1;
32 Q.push(v);
33 }
34 }
35 }
36 return d[t];
37 }
38
39 int main() {
40 scanf(%d%d%d,n,m,X);
41 int x,y,z;
42 for(int i 0; i m ;i){
43 scanf(%d%d%d,x,y,z);
44 //cinxyz;
45 e[x].push_back(make_pair(y,z));
46 //e[y].push_back(make_pair(x,z));
47 }
48
49 int ans 0;
50 for(int i 1 ;i n ;i){
51 if(i X){
52 continue;
53 }
54 int sum spfa(X,i);
55 sum spfa(i,X);
56 ans max(ans,sum);
57 }
58 coutansendl;
59
60 return 0;
61 } 转载于:https://www.cnblogs.com/Asumi/p/9716129.html
