汕尾住房和建设局网站,山西招标网,哪里有男男做受网站,误入网站退不了怎么做CF1473E Minimum Pathdescriptionsolutioncodedescription
题目链接
solution
看到 ∑i1kwei\sum_{i1}^kw_{e_i}∑i1kwei 的式子#xff0c;就应该联想到最短路
先考虑题目的弱化版#xff0c;去掉 max,min\text{max},\text{min}max,min 的限制#xff0c;变成一条…
CF1473E Minimum Pathdescriptionsolutioncodedescription
题目链接
solution
看到 ∑i1kwei\sum_{i1}^kw_{e_i}∑i1kwei 的式子就应该联想到最短路
先考虑题目的弱化版去掉 max,min\text{max},\text{min}max,min 的限制变成一条路径中的一条边不要花费一条边花费加倍再求最短路
贪心地 djikstra\text{djikstra}djikstra 跑最短路发现是与原题对应的
设 dpi,j,k(j,k∈[0,1])dp_{i,j,k}(j,k\in[0,1])dpi,j,k(j,k∈[0,1]) 表示到 iii 点时jjj 是否加倍了一条边kkk 是否不要一条边花费的最短路
则有转移方程 dpv,j,kmin(dpv,j,k,dpu,j,kwu,v)dp_{v,j,k}\min(dp_{v,j,k},dp_{u,j,k}w_{u,v}) dpv,j,kmin(dpv,j,k,dpu,j,kwu,v)
dpv,1,kmin(dpv,1,k,dpu,0,kwu,v∗2)dp_{v,1,k}\min(dp_{v,1,k},dp_{u,0,k}w_{u,v}*2) dpv,1,kmin(dpv,1,k,dpu,0,kwu,v∗2)
dpv,j,1min(dpv,j,1,dpu,j,0)dp_{v,j,1}\min(dp_{v,j,1},dp_{u,j,0}) dpv,j,1min(dpv,j,1,dpu,j,0)
最后答案为 min(dpi,0,0,dpi,1,1)\min(dp_{i,0,0},dp_{i,1,1})min(dpi,0,0,dpi,1,1) 【路径可能只有一条max,min\text{max},\text{min}max,min 相互抵消】
实际上也可以理解为把一个点拆成四个点后跑最短路
分别对应不同的操作先加倍再不要先不要再加倍
code
#include queue
#include cstdio
#include vector
#include iostream
using namespace std;
#define int long long
#define maxn 1000005
#define Pair pair int, int
priority_queue Pair, vector Pair , greater Pair q;
vector Pair G[maxn];
int n, m;
int dis[maxn];
bool vis[maxn];void addedge( int u, int v, int w ) { G[u].push_back( { v, w } ); }signed main() {scanf( %lld %lld, n, m );//分层图 [1,n]表示第一层 [n1,2n]表示使用加倍层 [2n1,3n]表示使用不要层 [3n1,4n]最后转移的结果层 //对应操作是加倍后不要x-xn-x3n 不要后加倍x-x2n-x3n for( int i 1, u, v, w;i m;i ) {scanf( %lld %lld %lld, u, v, w );addedge( u, v, w ), addedge( v, u, w );addedge( u n, v n, w ), addedge( v n, u n, w );addedge( u n * 2, v n * 2, w ), addedge( v n * 2, u n * 2, w );addedge( u n * 3, v n * 3, w ), addedge( v n * 3, u n * 3, w );addedge( u, v n, w * 2 ), addedge( v, u n, w * 2 ); //加倍 addedge( u, v n * 2, 0 ), addedge( v, u n * 2, 0 ); //不要 addedge( u n, v n * 3, 0 ), addedge( v n, u n * 3, 0 ); //加倍后不要 addedge( u n * 2, v n * 3, w * 2 ), addedge( v n * 2, u n * 3, w * 2 ); //不要后加倍 }for( int i 1;i ( n 2 );i ) dis[i] 1e18;q.push( { dis[1] 0, 1 } );while( ! q.empty() ) {int u q.top().second; q.pop();if( vis[u] ) continue;vis[u] 1;for( int i 0;i G[u].size();i ) {int v G[u][i].first, w G[u][i].second;if( dis[v] dis[u] w ) {dis[v] dis[u] w;q.push( { dis[v], v } );}}}for( int i 2;i n;i ) printf( %lld , min( dis[i], dis[i n * 3] ) );return 0;
}
