題目描述 最近，Elaxia和w的關係特別好，他們很想整天在一起，但是大學的學習太緊張了，他們 必須合理地安排兩個人在一起的時間。Elaxia和w每天都要奔波於宿舍和實驗室之間，他們 希望在節約時間的前提下，一起走的時間儘可能的長。 現在已知的是Elaxia和w**所在的宿舍和實驗室的編號以及學校的 ...
題目描述
最近，Elaxia和w的關係特別好，他們很想整天在一起，但是大學的學習太緊張了，他們 必須合理地安排兩個人在一起的時間。Elaxia和w每天都要奔波於宿舍和實驗室之間，他們 希望在節約時間的前提下，一起走的時間儘可能的長。 現在已知的是Elaxia和w**所在的宿舍和實驗室的編號以及學校的地圖：地圖上有N個路 口，M條路，經過每條路都需要一定的時間。 具體地說，就是要求無向圖中，兩對點間最短路的最長公共路徑。
輸入輸出格式
輸入格式：第一行：兩個整數N和M（含義如題目描述）。 第二行：四個整數x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分別表示Elaxia的宿舍和實驗室及w**的宿舍和實驗室的標號（兩對點分別 x1,y1和x2,y2）。 接下來M行：每行三個整數，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之間有一條路，經過這條路所需要的時間為l。
輸出格式：一行，一個整數，表示每天兩人在一起的時間（即最長公共路徑的長度）
輸入輸出樣例
輸入樣例#1：9 10 1 6 7 8 1 2 1 2 5 2 2 3 3 3 4 2 3 9 5 4 5 3 4 6 4 4 7 2 5 8 1 7 9 1輸出樣例#1：
3
說明
對於30%的數據，N ≤ 100；
對於60%的數據，N ≤ 1000；
對於100%的數據，N ≤ 1500，輸入數據保證沒有重邊和自環。
首先跑四遍SPFA求出各個點之間的最短路
然後暴力枚舉每一個點，跑出一個新的圖
再在圖上跑拓撲
找出最大值
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=200001; 8 int n,m; 9 int x11,y11,x22,y22; 10 struct node 11 { 12 int u,v,w,next; 13 }edge[MAXN],newedge[MAXN]; 14 int num=1; 15 int head[MAXN]; 16 int newnum=1; 17 int newhead[MAXN]; 18 int dis[5][MAXN]; 19 int vis[MAXN]; 20 int ans=0; 21 int rudu[MAXN]; 22 void SPFA(int k,int now) 23 { 24 queue<int>q; 25 memset(vis,0,sizeof(vis)); 26 memset(dis[now],0x7f,sizeof(dis[now])); 27 q.push(k);vis[k]=1;dis[now][k]=0; 28 while(q.size()!=0) 29 { 30 int p=q.front();q.pop(); 31 for(int i=head[p];i!=-1;i=edge[i].next) 32 { 33 int where=edge[i].u; 34 int to=edge[i].v; 35 if(dis[now][to]>dis[now][p]+edge[i].w) 36 { 37 dis[now][to]=dis[now][p]+edge[i].w; 38 if(vis[to]==0) 39 {vis[to]=1;q.push(to);} 40 } 41 } 42 } 43 /*for(int i=1;i<=n;i++) 44 cout<<dis[now][i]<<" "; 45 cout<<endl;*/ 46 } 47 void topsort() 48 { 49 int dis[MAXN]; 50 memset(dis,0,sizeof(dis)); 51 queue<int>q; 52 for(int i=1;i<=n;i++) 53 if(rudu[i]==0) 54 q.push(i); 55 while(q.size()!=0) 56 { 57 int p=q.front();q.pop(); 58 ans=max(ans,dis[p]); 59 for(int i=head[p];i!=-1;i=edge[i].next) 60 { 61 dis[newedge[i].v]=max(dis[newedge[i].v],dis[p]+newedge[i].w); 62 rudu[newedge[i].v]--; 63 if(rudu[newedge[i].v]==0) 64 q.push(newedge[i].v); 65 } 66 } 67 } 68 void build() 69 { 70 for(int i=1;i<=n;i++) 71 for(int j=head[i];j!=-1;j=edge[j].next) 72 { 73 int where=edge[j].u;int to=edge[j].v; 74 if(dis[1][i]+edge[j].w+dis[2][to]==dis[1][y11]&&dis[3][i]+edge[j].w+dis[4][to]==dis[3][y22]) 75 { 76 newedge[newnum].u=edge[j].u; 77 newedge[newnum].v=edge[j].v; 78 newedge[newnum].w=edge[j].w; 79 newedge[newnum].next=newhead[edge[newnum].u]; 80 rudu[newedge[newnum].v]++; 81 newhead[edge[newnum].u]=newnum++; 82 } 83 } 84 topsort(); 85 86 for(int i=1;i<=n;i++)newhead[i]=-1; 87 88 for(int i=1;i<=n;i++) 89 { 90 for(int j=head[i];j!=-1;j=edge[j].next) 91 { 92 int where=edge[j].u;int to=edge[j].v; 93 if(dis[1][i]+edge[j].w+dis[2][to]==dis[1][y11]&&dis[3][to]+edge[j].w+dis[4][i]==dis[3][y22]) 94 { 95 newedge[newnum].u=edge[j].u; 96 newedge[newnum].v=edge[j].v; 97 newedge[newnum].w=edge[j].w; 98 newedge[newnum].next=newhead[edge[newnum].u]; 99 rudu[newedge[newnum].v]++; 100 newhead[edge[newnum].u]=newnum++; 101 } 102 } 103 } 104 topsort(); 105 printf("%d",ans); 106 } 107 int main() 108 { 109 scanf("%d%d",&n,&m); 110 for(int i=1;i<=n;i++) 111 head[i]=-1, 112 newhead[i]=-1; 113 scanf("%d%d%d%d",&x11,&y11,&x22,&y22); 114 for(int i=1;i<=m;i++) 115 { 116 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w); 117 edge[num].next=head[edge[num].u]; 118 head[edge[num].u]=num++; 119 edge[num].u=edge[num-1].v; 120 edge[num].v=edge[num-1].u; 121 edge[num].w=edge[num-1].w; 122 edge[num].next=head[edge[num].u]; 123 head[edge[num].u]=num++; 124 } 125 SPFA(x11,1); 126 SPFA(y11,2); 127 SPFA(x22,3); 128 SPFA(y22,4); 129 build(); 130 return 0; 131 }感覺能AC但是只能過樣例的代碼
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 struct edge 6 { 7 int nxt,to,dis; 8 }a[3000010]; 9 int head[10000]; 10 int Head[10000]; 11 int lv[10000]; 12 bool b[10000]; 13 int s1[10000],t1[10000],s2[10000],t2[10000]; 14 int n,m,x1,y1,x2,y2,x,y,z,num,ans; 15 queue<int>q; 16 inline int max(int a,int b){return a>b?a:b;} 17 18 inline void add(int head[],int x,int y,int z) 19 {a[++num].nxt=head[x],a[num].to=y,a[num].dis=z,head[x]=num;} 20 21 inline void Add(int head[],int x,int y,int z){add(head,x,y,z);add(head,y,x,z);} 22 inline void SPFA(int S,int dis[]) 23 { 24 memset(dis,0x3f,sizeof (int)*1510); 25 dis[S]=0;q.push(S); 26 while(!q.empty()) 27 { 28 int tmp=q.front();q.pop(); 29 b[tmp]=0; 30 for(int i=head[tmp];i;i=a[i].nxt) 31 if(dis[a[i].to]>dis[tmp]+a[i].dis) 32 { 33 dis[a[i].to]=dis[tmp]+a[i].dis; 34 if(!b[a[i].to]) b[a[i].to]=1,q.push(a[i].to); 35 } 36 } 37 } 38 inline void topologysort() 39 { 40 int dis[10000]; 41 memset(dis,0,sizeof(dis)); 42 for(int i=1;i<=n;i++) 43 if(!lv[i]) q.push(i); 44 while(!q.empty()) 45 { 46 int tmp=q.front();q.pop(); 47 ans=max(ans,dis[tmp]); 48 for(int i=Head[tmp];i;i=a[i].nxt) 49 { 50 dis[a[i].to]=max(dis[a[i].to],dis[tmp]+a[i].dis); 51 if(!--lv[a[i].to]) q.push(a[i].to); 52 } 53 } 54 } 55 int main() 56 { 57 scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2); 58 for(int i=1;i<=m;i++) 59 scanf("%d%d%d",&x,&y,&z),Add(head,x,y,z); 60 SPFA(x1,s1);SPFA(y1,t1); 61 SPFA(x2,s2);SPFA(y2,t2); 62 63 for(int tmp=1;tmp<=n;tmp++) 64 for(int i=head[tmp];i;i=a[i].nxt) 65 if(s1[tmp]+a[i].dis+t1[a[i].to]==s1[y1]&&s2[tmp]+a[i].dis+t2[a[i].to]==s2[y2]) 66 add(Head,tmp,a[i].to,a[i].dis),lv[a[i].to]++; 67 topologysort(); 68 69 memset(Head,0,sizeof(Head)); 70 for(int tmp=1;tmp<=n;tmp++) 71 for(int i=head[tmp];i;i=a[i].nxt) 72 if(s1[tmp]+a[i].dis+t1[a[i].to]==s1[y1]&&s2[a[i].to]+a[i].dis+t2[tmp]==s2[y2]) 73 add(Head,tmp,a[i].to,a[i].dis),lv[a[i].to]++; 74 topologysort(); 75 printf("%d",ans); 76 return 0; 77 }AC
