题目:
经过努力,LCJ终于获得了一个带薪假期。他准备要在N个城市中挑选若干个进行旅游,其中有K个城市他是一定要去的。然而他英(qi)明(guai)的上司KID向他提出了一个要求,因为经费的问题,他的旅行路线必须是某两个城市之间的一条最短路。现在LCJ就要在这N个城市之间的道路找到这样一条路线:它是一条某两个城市之间的最短路,经过了K个特殊的城市,在满足条件的路线中,找到最短的一条。
输入
第一行两个数N,M。表示有N座城市,M条边。
接下来M行每行三个数xi,yi,vi,表示有一条长度为vi的双向路径连接对应的两座城市。
接下来一个数K。
接下来一行K个数,表示一定要经过的城市。
输出
一个数,符合要求的最短最短路长度。
样例输入
6 6
1 2 2
2 6 2
1 3 1
3 4 1
4 5 1
5 6 1
3
5 1 3
样例输出
3
对于30%的数据,1<=N<=10,1<=M<=20
对于60%的数据,1<=N<=500,1<=M<=1000。
对于100%的数据,1<=N<=100000,1<=M<=300000,1<=vi<=10000,1<=K<=N,保证有解。
这道题看了下题解,不明觉厉,然后听了zyf大神自己yy的算法:
1.在需要走到的点(下文称要点)中取一个点P
2.以P做一遍单源最短路,找到离它最远的要点Q
3.再以Q做一遍单源最短路,找到离他最远的要点M,答案就是dist(Q,M)
证明:
对于原题要求的路径必须是两点之间的最短路,可以肯定,这两个点都是要点,对于点Q,明显是路径的一个起点,而M,就是另一个起点,题目有保证有解,所以答案就是dist(Q,M)
#include<cstdio> #include<cstring> #include<iostream> const int maxn=100010,maxm=600010; using namespace std; int tot=0; int pre[maxm],son[maxm],v[maxm]; int now[maxn]; inline void add(int a,int b,int c){ pre[++tot]=now[a]; now[a]=tot; son[tot]=b; v[tot]=c; } void cc(int a,int b,int c){ add(a,b,c); add(b,a,c); } inline int getint(){ char ch=getchar(); int tmp=0; while (ch<'0' || ch>'9') ch=getchar(); for (;ch<='9' && ch>='0';ch=getchar()) tmp=tmp*10+ch-'0'; return tmp; } int h[maxn]; int f[maxn]; bool b[maxn]; void spfa(int x){ int t=0,w=1; h[1]=x; memset(f,63,sizeof(f)); memset(b,0,sizeof(b)); b[x]=1; f[x]=0; while (t!=w){ if (++t==maxn) t=1; for (int p=now[h[t]];p;p=pre[p]) if (f[h[t]]+v[p]<f[son[p]]){ f[son[p]]=f[h[t]]+v[p]; if (!b[son[p]]){ b[son[p]]=1; if (++w==maxn) w=1; h[w]=son[p]; int tt=t+1; if (tt==maxn) tt=1; if (f[h[tt]]>f[h[w]]) swap(h[tt],h[w]); } } b[h[t]]=0; } } int ne[maxn]; int main(){ int n=getint(); int m=getint(); for (int i=1;i<=m;++i){ int a=getint(),b=getint(),c=getint(); cc(a,b,c); } int k=getint(); for (int i=1;i<=k;++i) ne[i]=getint(); spfa(ne[1]); int ptmp=ne[1],tmp=0; for (int i=1;i<=k;++i) if (f[ne[i]]>tmp){ ptmp=ne[i]; tmp=f[ne[i]]; } spfa(ptmp); int ans=0; for (int i=1;i<=k;++i) ans=max(ans,f[ne[i]]); printf("%d\n",ans); return 0; }