题解：P6822 [PA 2012 Finals] Tax

· · 题解

非常非常好的一道建图的题。

首先注意到对着点做是困难的，因此，我们考虑对着边做。

我们不妨给边进行编号，同时对于连接同样两个点的不同方向的边，我们考虑用 id 和 id \oplus 1 的形式进行编号。方便得到反边。

接下来的一切操作都是基于边构成的图进行操作。如果有和点有关的，会特别指出。

由于 a\rightarrow b \rightarrow c 的路径由 a,c 共同决定，因此当我们走到 b\rightarrow c 这条边的时候，我们也需要知道是从那条边到达的。但是很显然，如果说我们直接把边 a\rightarrow b 连向 b\rightarrow c 的话，这个问题其实又退化成最初始的问题了，显然不正确。

但是我们注意到 a\rightarrow b 的反边 b\rightarrow a 是和 b\rightarrow c 这条边都隶属于点 b 的换边系统。因此，从 b\rightarrow a 到 b \rightarrow c 是好处理的。

因此，我们考虑 a\rightarrow b 向 b \rightarrow a 连边，这一步可以直接用 id\oplus 1 的方式完成。然后 b \rightarrow a 向 b \rightarrow c 连边即可。

然后考虑边权的问题。

我们不妨这样考虑：我们设 w_i 表示 b \rightarrow a 的边权，w_j 表示 b \rightarrow c 的边权。很显然，若 w_i > w_j，那么此时对于点 a \rightarrow b \rightarrow c 的路径之和为 w_i，反之则为 w_j。由于从 a\rightarrow b 到 b \rightarrow a 的路径是铁打的事实，所以说这一条边的边权就一定设为 w_i，然后考虑 b \rightarrow a 到 b \rightarrow c 的边权如何设定。

很显然，这里需要分情况讨论。若 w_i<w_j，那么 b \rightarrow a 到 b \rightarrow c 的边权就应该为 w_j-w_i，反之应该为 0。

因此，我们不妨直接对着 b 的换边系统按照边权从小到大进行排序，然后将相邻的两条边（假设编号分别为 x,y，其中 x 排序后在 y 之前）进行连边即可，具体点为 x \rightarrow y，边权为 w_y-w_x；y \rightarrow x，边权为 0。

注意到我们还没有处理起点和终点，我们不妨设 0 号节点为超级源点，1 号节点为超级汇点，然后简单处理一下即可。

最后在新图上跑 Dijkstra 即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int INF=1e5+10;

int n,m,cnt=1,s,t;
struct Node{int u,w,id;};
struct Pair{
    int u,w;
    bool operator <(const Pair a1)const{
        return a1.w<w;
    }
};
vector<Pair> G[INF<<2];
vector<Node> mp[INF];

bool cmp(const Node a1,const Node a2){return a1.w<a2.w;}
int dis[INF<<2];
bool book[INF<<2];
void dij(int st){
    priority_queue<Pair> q;
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    q.push({st,0});
    while (!q.empty()){
        int u=q.top().u;q.pop();
        if (book[u])continue;
        book[u]=1;
        for (Pair v:G[u]){
            if (dis[v.u]>dis[u]+v.w){
                dis[v.u]=dis[u]+v.w;
                q.push({v.u,dis[v.u]});
            }
        }
    }
}
signed main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        mp[a].push_back({b,c,++cnt});
        mp[b].push_back({a,c,++cnt});
    }
    s=0,t=1;
    for (Node v:mp[1])G[0].push_back({v.id,v.w});
    for (Node v:mp[n])G[v.id^1].push_back({t,v.w});
    for (int i=1;i<=n;i++)for (Node v:mp[i])G[v.id].push_back({v.id^1,v.w});
    for (int i=1;i<=n;i++){
        if (mp[i].empty())continue;
        sort(mp[i].begin(),mp[i].end(),cmp);
        int len=mp[i].size()-1;
        for (int j=0;j<len;j++){
            int u=mp[i][j].id,v=mp[i][j+1].id,w1=mp[i][j].w,w2=mp[i][j+1].w;
            G[u].push_back({v,w2-w1});
            G[v].push_back({u,0});
        }
    }
    dij(s);
    cout<<dis[t];
    return 0;
}