别忘了无向图边开2e5*2
题意：给一个无向图，有n个点和m个边，其中包含k个特殊的点。现在让任意两个特殊的点中间连线，求1到n的最大的最短路是多少。
思路：定义两个数组d1,d2分别储存从1和从n到各各点储存的最短路长度。
1.如果连接的两个点之间连线不影响结果ans，则ans为d1[n]
2.如果这两个点影响，设这两个点分别为a，b。ans = min(d1[a]+d2[b]+1,d2[a]+d1[b]+1)
则问题转化为
给两个长度为n的数组a，b。
如何在O（n）的复杂度求出i和j（i！=j）
使得min（ai+bj，aj+bi）最大。
假若让ai+bj<aj+bi ，所以ai-bi<bj-aj.。
可以领两个数组根据ai-bi进行排序，遍历1-n，当遍历到posj的时候，最优解posi为【1-posj-1】的最大a的下标，随便维护一下即可。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> // #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define sp ' ' #define endl ' ' #define inf 0x3f3f3f3f #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl #define P pair<int, int> #define fi first #define se second #define pb(x) push_back(x) #define ppb() pop_back() #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define rep(i,a,b) for(int i=a;i<=b;i++) #define repd(i,a,b) for(int i=a;i>=b;i--) #define sca3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define sca2(a,b) scanf("%d %d",&(a),&(b)) #define sca(a) scanf("%d",&(a)); #define sca3ll(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c)) #define sca2ll(a,b) scanf("%lld %lld",&(a),&(b)) #define scall(a) scanf("%lld",&(a)); using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a, ll b, ll mod){ll sum = 1;while (b) {if (b & 1) {sum = (sum * a) % mod;b--;}b /= 2;a = a * a % mod;}return sum;} const double Pi = acos(-1.0); const double epsilon = Pi/180.0; const int maxn = 4e5+10; int n,m,k; int ver[maxn],head[maxn],nextt[maxn],vis[maxn],edge[maxn*2]; priority_queue<pair < int,int> >que; priority_queue<pair < int,int> >que2; int tot; int d1[maxn],d2[maxn]; int spe[maxn]; void add(int x,int y,int z) //邻接矩阵，x是这条边的起点，y是终点，z是长度 { ver[++tot]=y,edge[tot]=z; nextt[tot]=head[x],head[x]=tot; } void dijkstra1(int origin) //求origin到各个点的最短长度 { memset(d1,9999999,sizeof(d1)); memset(vis,0,sizeof(vis)); d1[origin]=0; que.push(make_pair(0,origin)); while(que.size()) { int x=que.top().second; que.pop(); if(vis[x]==1) continue; vis[x]=1; for(int i=head[x];i;i=nextt[i]) { int y=ver[i]; int z=edge[i]; if(d1[y]>d1[x]+z) { d1[y]=d1[x]+z; que.push(make_pair(-d1[y],y)); } } } } void dijkstra2(int origin) //求origin到各个点的最短长度 { memset(d2,9999999,sizeof(d2)); memset(vis,0,sizeof(vis)); d2[origin]=0; que.push(make_pair(0,origin)); while(que.size()) { int x=que.top().second; que.pop(); if(vis[x]==1) continue; vis[x]=1; for(int i=head[x];i;i=nextt[i]) { int y=ver[i]; int z=edge[i]; if(d2[y]>d2[x]+z) { d2[y]=d2[x]+z; que.push(make_pair(-d2[y],y)); } } } } struct node { int id,x; }p[maxn]; bool cmp(node a,node b) { return a.x<b.x; } int a[maxn]; int main() { //freopen("input.txt", "r", stdin); cin>>n>>m>>k; rep(i,1,k){ cin>>a[i]; } rep(i,1,m){ int x,y; cin>>x>>y; add(x,y,1); add(y,x,1); } dijkstra1(1); dijkstra2(n); rep(i,1,k) { p[i].id=a[i]; p[i].x=d1[a[i]]-d2[a[i]]; } sort(p+1,p+1+k,cmp); int maxx = 0,ans = 0; for (int i=1;i<=k;i++) { int num=p[i].id; // cout<<num<<endl; if (i==1)maxx=d1[num]; else { //cout<<maxx<<sp<<d2[num]<<endl; ans=max(ans,maxx+d2[num]+1); maxx=max(maxx,d1[num]); } // cout<<ans<<endl; } cout<<min(ans,d1[n]); }