太弱了。。。

一開始看到題感覺是跑一個最小生成樹在上邊進行LCA就行了，但是發現過不了樣例，然后就是就想到了之前做過類似做法的題目，就是非生成樹上的邊最多只有21條，然后就那些邊記錄下來，通過每一條邊的兩個點跑lca然后取最小值

 ll ans=lca(x,y);for(int i=1;i<=k;i++)           {ans=min(ans,b[i].val+lca(x,b[i].x)+lca(y,b[i].y));ans=min(ans,b[i].val+lca(x,b[i].y)+lca(y,b[i].x));}cout<<ans<<endl;

這樣發現也不行，想明白了之后你要求的可能是某兩個點由多條非生成樹邊連接并且最短，emmm然后就沒辦法做了，沒有想到轉化成為這些非生成樹邊的點（最多42個）每一個點到兩個詢問點的距離，其實也就是跑40多次的最短路，用dij就可以卡過去。

我的做法就是先用kuske建立一個生成樹（好像沒有必要用kuske提出來最短邊），跑dfs用倍增提前記錄好父親節點以備跑lca，然后記錄其他沒有在生成樹里的邊上的點，然后從這些點出發跑最短路，以Dis[i][x]記錄第i個點到x的最短距離，然后詢問x,y的最短路，就是將lca(x,y)與每一個Dis[i][x]+Dis[i][y]進行比較取最小值，即可得出答案。

代碼如下

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define pii make_pair
#define pli pair<long long,int >
const int dir[4][2]= {0,-1,-1,0,0,1,1,0};
typedef long long ll;
const ll inFF=9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=2e5+5;
int f[maxn][30],d[maxn],head[maxn];
int fa[maxn];
ll dis[maxn],Dis[50][maxn];
int vis[maxn],mm[50];
int sign,n,m,q,cnt;
map<ll,int>mp;
struct node
{int to,p;ll val;
}edge[maxn<<1];
struct nod
{int x,y;ll val;
}a[maxn];
struct eg {ll val;int next;bool friend operator<(eg q,eg e){return q.val>e.val;}
};
vector<eg>v[maxn];
bool cmp(nod s,nod e)
{return s.val<e.val;
}
void add(int u,int v,ll val)
{edge[sign]=node{v,head[u],val};head[u]=sign++;
}
int find(int x)
{if(x==fa[x]) return x;else return fa[x]=find(fa[x]);
}
void init()
{sign=cnt=0;mp.clear();for(int i=0;i<=n;i++){fa[i]=i;head[i]=-1;v[i].clear();}
}
void kuske()
{for(int i=1;i<=m;i++){int fx=find(a[i].x);int fy=find(a[i].y);int x=a[i].x,y=a[i].y;ll val=a[i].val;if(fx!=fy){fa[fx]=fy;add(a[i].x,a[i].y,a[i].val);//這是取出生成樹的邊跑倍增，其實可以直接dfs跑出來add(a[i].y,a[i].x,a[i].val);} else{if(mp[x]==0) mp[x]=++cnt,mm[cnt]=x;//記錄那些點的順序if(mp[y]==0) mp[y]=++cnt,mm[cnt]=y;}v[x].push_back(eg{val,y});//所有的邊都加到里邊跑dijv[y].push_back(eg{val,x});}
}
void dij(int id,int s)//跑出來Dis[i][x]第i點到每個點的最小距離
{for(int i=0;i<maxn;i++){vis[i]=0;Dis[id][i]=inFF;}Dis[id][s]=0;priority_queue<eg >q;q.push(eg{0,s});while(!q.empty()){eg now=q.top();q.pop();int u=now.next;if(now.val>Dis[id][u]) continue;vis[u]=1;//cout<<mm[id]<<"->"<<now.next<<" "<<Dis[id][u]<<endl;for(int i=0;i<v[u].size();i++){int next=v[u][i].next;ll val=v[u][i].val;if(vis[next]) continue;if(Dis[id][next]>Dis[id][u]+val){Dis[id][next]=Dis[id][u]+val;q.push(eg{Dis[id][next],next});}}}
}
void dfs(int u)
{for(int i=1;(1<<i)<=n;i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=head[u];~i;i=edge[i].p){int v=edge[i].to;if(v==f[u][0]) continue;d[v]=d[u]+1;f[v][0]=u;dis[v]=dis[u]+edge[i].val;dfs(v);}
}
ll lca(int a,int b)//lca模板
{int s=a,e=b;if(d[a]<d[b]) swap(a,b);int x=d[a]-d[b];for(int i=0;(1<<i)<=x;i++)if((1<<i)&x) a=f[a][i];if(a!=b){for(int i=(int)log2(n);i>=0;i--)if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];a=f[a][0];}ll ans=dis[s]+dis[e]-2*dis[a];return ans;
}
int main()
{int x,y;while(cin>>n>>m){init();for(int i=1;i<=m;i++)scanf("%d %d %lld",&a[i].x,&a[i].y,&a[i].val);sort(a+1,a+1+m,cmp);kuske();for(int i=1;i<=cnt;i++)dij(i,mm[i]);f[1][0]=1,d[1]=0,dis[1]=0;dfs(1);cin>>q;while(q--){scanf("%d %d",&x,&y);ll ans=lca(x,y);for(int i=1;i<=cnt;i++)ans=min(ans,Dis[i][x]+Dis[i][y]);printf("%lld\n",ans);}}return 0;
}

?

總結

以上是生活随笔為你收集整理的The Shortest Statement CodeForces - 1051F LCA+最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。