E - Minimum Path

分層圖最短路
第一個分層圖
第0層就是按照題中給的點連邊，從第0層到第1層我們連一條邊權是0的邊，從第1層到第2層連一條邊權是原先邊權2倍的邊，當然第1層以及第2層之間按照原圖連邊。
第二個分層圖
第0層就是按照題中給的點連邊，從第0層到第1層我們連一條邊權是原先邊權2倍的邊，從第1層到第2層連一條邊權0的邊，當然第1層以及第2層之間按照原圖連邊。

然后最終答案在兩個分層圖的第二層比較。如果從1到某個點只存在一條邊，那么最短路應該與第0層的答案相同，再順便比較一下即可。

為什么有兩個分層圖？
第一個分層圖我們從0—>1層花費是0代表少經過一條邊，從1—>2層花費原先兩倍邊權，兩者結合代表用一條邊的邊權代替另一題邊的邊權。而這樣建圖表示最長邊出現在最短邊之前。
而第二個分層圖代表最短邊出現最長邊之前。而所有點的最短路無非這兩種情況。

對于一條路徑我們沒考慮減去最大值加上最小值，而是用一條路邊替另一條邊，而最短路徑一定是最小的邊代替最長的邊

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<bitset> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<ll,int> pli; const int N=600010; const int M=4000010; int h1[N],h2[N],e[M],ne[M],idx; int n,m; ll w[M],d1[N],d2[N]; bool st[N]; void add(int h[],int a,int b,ll c) {e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++; } void dijkstra(int h[],ll dist[]) {//memset(dist,0x3f,8*N);memset(st,0,sizeof st);dist[1]=0;priority_queue<pli,vector<pli>,greater<pli> >q;q.push({0,1});while(q.size()){ll d=q.top().first,t=q.top().second;q.pop();if(st[t]) continue;st[t]=1;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>d+w[i]) {dist[j]=d+w[i];q.push({dist[j],j});}}} }int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m;memset(h1,-1,sizeof h1);memset(h2,-1,sizeof h2);memset(d1,0x3f,sizeof d1);memset(d2,0x3f,sizeof d2);while(m--){int a,b,c;cin>>a>>b>>c;add(h1,a,b,c),add(h1,b,a,c);add(h1,a+n,b+n,c),add(h1,b+n,a+n,c);add(h1,a+2*n,b+2*n,c),add(h1,b+2*n,a+2*n,c);add(h1,a,b+n,0);add(h1,b,a+n,0);add(h1,a+n,b+2*n,2*c);add(h1,b+n,a+2*n,2*c);add(h2,a,b,c),add(h2,b,a,c);add(h2,a+n,b+n,c),add(h2,b+n,a+n,c);add(h2,a+2*n,b+2*n,c),add(h2,b+2*n,a+2*n,c);add(h2,a,b+n,2*c);add(h2,b,a+n,2*c);add(h2,a+n,b+2*n,0);add(h2,b+n,a+2*n,0);}dijkstra(h1,d1);dijkstra(h2,d2);for(int i=2;i<=n;i++)cout<<min(min(d1[i],d1[i+2*n]),d2[i+2*n])<<' ';cout<<'\n';}return 0; }

可惜和隊友想出做法的時候就剩10分鐘了，沒能完成可惜可惜

總結

以上是生活随笔為你收集整理的codeforces1473 E.Minimum Path（分层图最短路）的全部內容，希望文章能夠幫你解決所遇到的問題。

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