E. Minimum Path 分层图最短路径
题目大意:
给你一张n个点m条边的图,对于一条路径的权值等于,这条路经过的所有的边的权值之和加上最短的边的权值,再减去最长的边的权值,问:从点1到其他所有的点的权值最短分别是多少。
题解:
这个题目一看就知道是一个最短路,但是因为有了一个加一个减的限制,所以不是普通的最短路,而是对最短路进行了变形,自己写了蛮久还没有过之后,上网查了一下题解,题解说是:分层图最短路径,然后简单的看了这个算法,好像就两种解法,一种是dp
,还有一种是拆点。
我就用dp
的解法来试试
状态的定义是:\(dis[u][1/0][1/0]\) 表示的是到 u
这个点,加的操作是否用过,减的操作是否用过,最后答案就是 \(dis[u][1][1]\) 。
状态转移,从 \(dis[u][x][y]\)
- \(dis[v][x][y] = dis[u][x][y]+w\) 直接转移
- x = 0, \(dis[v][1][y] = dis[u][x][y]+2*w\)
- y = 0, \(dis[v][x][1] = dis[u][x][y]\)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
long long w[maxn];
int head[maxn],to[maxn],nxt[maxn],cnt;
void add(int u,int v,int c){
cnt++,to[cnt] = v,w[cnt] = c,nxt[cnt] = head[u],head[u] = cnt;
cnt++,to[cnt] = u,w[cnt] = c,nxt[cnt] = head[v],head[v] = cnt;
}
struct node{
ll d;
int u,x,y;
node(int u=0,ll d=0,int x=0,int y=0):u(u),d(d),x(x),y(y){}
bool operator<(const node &a)const{
return a.d<d;
}
};
priority_queue<node>que;
ll dis[maxn][2][2];
bool vis[maxn][2][2];
void dij(int s){
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s][0][0] = 0;
que.push(node(s,0,0,0));
while(!que.empty()){
node x = que.top();que.pop();
if(vis[x.u][x.x][x.y]) continue;
// printf("u = %d x = %d y = %d d = %lld\n",x.u,x.x,x.y,x.d);
vis[x.u][x.x][x.y] = true;
for(int i=head[x.u];i;i=nxt[i]){
int v = to[i];
ll tmp = dis[x.u][x.x][x.y];
if(dis[v][x.x][x.y]>tmp+w[i]){
dis[v][x.x][x.y] = tmp+w[i];
que.push(node(v,dis[v][x.x][x.y],x.x,x.y));
}
if(!x.x&&dis[v][1][x.y]>tmp+2*w[i]){
dis[v][1][x.y] = tmp+2*w[i];
que.push(node(v,dis[v][1][x.y],1,x.y));
}
if(!x.y&&dis[v][x.x][1]>tmp){
dis[v][x.x][1] = tmp;
que.push(node(v,dis[v][x.x][1],x.x,1));
}
if(!x.x&&!x.y&&dis[v][1][1]>tmp+w[i]){
dis[v][1][1] = tmp + w[i];
que.push(node(v,dis[v][1][1],1,1));
}
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
}
dij(1);
for(int i=2;i<=n;i++){
printf("%lld",dis[i][1][1]);
if(i==n) printf("\n");
else printf(" ");
}
return 0;
}