题目链接 – P6822 [PA2012] Tax画图工具

题目描述

给出一个 n 个点 m 条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点 1 到点 n 的最小代价。起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权。

输入格式

第一行两个数 n,m,分别表示点数和边数。

接下来 m 行,每行三个数 a,b,c,表示 a,b 之间存在一条长度为 c 的边。

输出格式

一行一个数,表示答案。

样例 #1
样例输入 #1
4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8
样例输出 #1
12
数据范围

1\leq n\leq 10^51\leq m\leq 2\times 10^51\leq c\leq 10^6

题目分析

1. Dijkstra算法的可用性

我们先看看Dij算法可不可以直接跑:

Alt

1号点开始,先扩展到最近的邻居,此时问题来了,从邻居出发走到下一站的时候会改变从起点走到邻居的费用,这样就不知道第一次该怎么找最优的邻居,不符合Dijkstra算法思路。

2.建新图

1号点出发,有一个出发的费用,而经过一个点,也就是从边到边,有另一个费用;从起点到终点,收了边数 + 1次费用。 由此我们可以想到,可以建一个新图,原图中的每条边都可以变成两个点,这两个点可以以该条边的费用双向互通;再加入一个起点、一个终点,新的图就建好了。 但是这样会有一个问题:如果碰到菊花图,那会有m^2条新边,这明显不符合题目的数据范围。

3.优化

从一个点出发,从不同的边来到不同的边上费用都不一样,那么恰好,让点的出边排序,这些出边的权值依次上升,权值升高时,路径换了,走到了不同的边。对这些边的权值进行差分处理,升级就建立两边差值的边,降级就建立费用为0的边。如果要继续走下去,在这条边上只能换向(也就是再加上这条边的费用),可以发现,到下一个点的时候,(换向后)的边已经是下一个点的出边,在换边的时候,如果换的边费用更低,就走一条费用为0的路,如果费用更高,就走一条排序后差分处理的边。

这个时候从S点开始跑最短路,由于只有所有出边之间建立了路径,路径的总量约为2*m

AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e5 + 10;
const int U = 4e5 + 10;
const int M = 5e6 + 10;
const ll LL_INF = 0x3f3f3f3f3f3f3f3fLL;
int head[U];
int n, m, s, t;
//新图的边
struct edge{
  int to, width, nxt;
}mp[M];
int cnt = 1;
//链式前向星
inline void add_edge(int u, int v, int w) {
  mp[cnt] = (edge){v, w, head[u]};
  head[u] = cnt++;
}
//老图的点
struct node{
  int id, to, width;
  bool operator< (const node &x) const {
    return x.width > width;
  }
};
vector<node> G[N];
bool done[M];
ll dis[M];
inline void dij() {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  priority_queue<pair<ll, int>> q;
  q.push({0, s});
  while(!q.empty()) {
    int now = q.top().second;
    q.pop();
    if(done[now]) continue;
    done[now] = true;
    for(int i = head[now]; i != -1; i = mp[i].nxt) {
      int to = mp[i].to;
      int w = mp[i].width;
      if(dis[to] > dis[now] + w) {
        dis[to] = dis[now] + w;
        q.push({-dis[to], to});
      }
    }
  }
  ll ans = LL_INF;
  for(auto i : G[n]) {
    ans = min(ans, dis[i.id]);
  }
  printf("%lld\n", ans);
}
int u, v, w;
int main()
{
  scanf("%d%d", &n, &m);
  memset(head, -1, sizeof(head));
  for(int i = 0; i < m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    G[u].emplace_back((node){i << 1 | 1, v, w});
    G[v].emplace_back((node){i << 1, u, w});
    add_edge(i << 1, i << 1 | 1, w);
    add_edge(i << 1 | 1, i << 1, w);
  }
  s = m * 2;
  t = m * 2 + 1;
  for(auto i : G[1]) {
    add_edge(s, i.id, i.width);
  }
  for(auto i : G[n]) {
    add_edge(i.id, t, i.width);
  }
  for(int i = 1; i <= n; i++) {
    sort(G[i].begin(), G[i].end());
    int sz = G[i].size();
    for(int j = 0; j < sz - 1; j++) {
      add_edge(G[i][j].id, G[i][j + 1].id, G[i][j + 1].width - G[i][j].width);
      add_edge(G[i][j + 1].id, G[i][j].id, 0);//加边
    }
  }
  dij();
  return 0;
}