本文主要是介绍hdu2833 WuKong，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定两个起点终点，求两条最短路径上的最多交集点数。
求了最短路之后，枚举两条路上每条必然属于最短路径上的路径，（d[u]+w==d[v]，则该条路径必然在最短路径上）
dp[a][b]表示以a b为终点的最多交集点数。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll long long
const int maxn=310;
const int maxm=90010;
using namespace std;struct node
{int v,w,next;
}e[maxm<<1];
int vis[maxn],dp[maxn][maxn],h,head[maxn],n,m,d1[maxn],d2[maxn];void addedge(int a,int b,int c)
{e[h].v=b;e[h].w=c;e[h].next=head[a];head[a]=h++;
}void spfa(int s,int t,int d[])
{int x,v,w,i;memset(vis,0,sizeof vis);d[s]=0,vis[s]=1;queue<int> q;q.push(s);while(!q.empty()){x=q.front();q.pop();vis[x]=0;for(i=head[x];i!=-1;i=e[i].next){v=e[i].v;w=e[i].w;if(d[v]>d[x]+w){d[v]=d[x]+w;if(!vis[v]){vis[v]=1;q.push(v);}}}}return ;
}int dfs(int s,int t)
{if(dp[s][t]!=-1) return dp[s][t];int i,j,tmp=0;if(s==t){tmp++;for(i=head[s];i!=-1;i=e[i].next){if(d1[e[i].v]+e[i].w!=d1[s]) continue;for(j=head[t];j!=-1;j=e[j].next){if(d2[e[j].v]+e[j].w!=d2[t]) continue;tmp=max(tmp,dfs(e[i].v,e[j].v)+1);}}}for(i=head[s];i!=-1;i=e[i].next){if(d1[e[i].v]+e[i].w==d1[s])tmp=max(tmp,dfs(e[i].v,t));}for(i=head[t];i!=-1;i=e[i].next){if(d2[e[i].v]+e[i].w==d2[t])tmp=max(tmp,dfs(s,e[i].v));}return dp[s][t]=tmp;
}int main()
{int a,b,c,s1,s2,e1,e2;while(scanf("%d%d",&n,&m)&&(n||m)){h=0;memset(head,-1,sizeof head);while(m--){scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);addedge(b,a,c);}scanf("%d%d%d%d",&s1,&e1,&s2,&e2);memset(d1,0x3f,sizeof d1);spfa(s1,e1,d1);memset(d2,0x3f,sizeof d2);spfa(s2,e2,d2);memset(dp,-1,sizeof dp);dp[s1][s2]=(s1==s2);printf("%d\n",dfs(e1,e2));}return 0;
}
这篇关于hdu2833 WuKong的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
