题：https://codeforces.com/contest/1473/problem/E

题意：求减掉最长边加上最短边的最短路

分析：多出了俩维，第一维0/1：是否去掉这条边，第二维0/1：是否加上这条边，答案就是套上dij后的dis[ i ] [ 1 ] [ 1 ]

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
#define UM unordered_map
typedef long long ll;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
#define pi 3.1415926535898
#define DEC (pi/180)
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
#define lc root<<1
#define rc root<<1|1
const int M=2e5+5;
ll dis[M][2][2];
int book[M][2][2];
vector< pair<int,ll> >g[M];
void pn(){
    puts("NO");
}
void py(){
    puts("YES");
}
struct node{
    int u,f0,f1;
    ll w;
    node(int u,int f0,int f1,ll w):u(u),f0(f0),f1(f1),w(w){}
    bool operator < (const node &b)const{
        return w>b.w;
    }
};
priority_queue<node>que;
void Dij(int n){
    for(int i=1;i<=n;i++)
        for(int j=0;j<=1;j++)
            for(int k=0;k<=1;k++) dis[i][j][k]=INF;
    while(!que.empty()) que.pop();
    que.push(node(1,0,0,0));
    dis[1][0][0]=0;
    while(!que.empty()){
        node now=que.top(); que.pop();
        int u=now.u,f0=now.f0,f1=now.f1;
        ll cost=now.w;
        if(book[u][f0][f1]) continue;
        book[u][f0][f1]=1;
        for(auto it:g[u]){
            int v=it.first;
            ll w=it.second;
            if(dis[v][f0][f1]>cost+w){
                dis[v][f0][f1]=cost+w;
                que.push(node(v,f0,f1,dis[v][f0][f1]));
            }
            if(f0==0&&dis[v][1][f1]>cost){
                dis[v][1][f1]=cost;
                que.push(node(v,1,f1,dis[v][1][f1]));
            }
            if(f1==0&&dis[v][f0][1]>cost+2*w){
                dis[v][f0][1]=cost+2*w;
                que.push(node(v,f0,1,dis[v][f0][1]));
            }
            if(f0==0&&f1==0&&dis[v][1][1]>cost+w){
                dis[v][1][1]=cost+w;
                que.push(node(v,1,1,dis[v][1][1]));
            }
        }
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int u,v,i=1;i<=m;i++){
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        g[u].pb(MP(v,w));
        g[v].pb(MP(u,w));
    }
    Dij(n);
    for(int i=2;i<=n;i++)
        printf("%lld ",dis[i][1][1]);
    return 0;
}

View Code