Roadblocks题解

· · 题解

因为不久前刚刚看过了最短路计数这道题目，所以就想在求最短路的时候，用dis数组记录最短路和次短路，然后就愉快的打完了代码，过了样例，但是只有50分。 然后，我重新想了想我在求最短路的时候的判断，发现50这个样子写，最小值可能会覆盖次小值，因为我只判断了一遍的范围，没有限制次小值严格小于最小值。而且题目要求一条路可以重复走多次，所以我增加了每个点可以经过的次数。 判断部分就改成了下面这样

for (int i = head[id]; i; i = e[i].nxt)
{
    if (dis[e[i].v][0] > di + e[i].w)
    {
        dis[e[i].v][1] = dis[e[i].v][0], dis[e[i].v][0] = di + e[i].w;
        if (dis[e[i].v][1] > dis[id][1] + e[i].w && dis[e[i].v][0] < dis[id][1] + e[i].w)
        dis[e[i].v][1] = dis[id][1] + e[i].w;
        if (vis[e[i].v] < 2) q.push(make_pair(dis[e[i].v][0], e[i].v));
    }
    else
        if (dis[e[i].v][1] > di + e[i].w && dis[e[i].v][0] < di + e[i].w)
        {
            dis[e[i].v][1] = di + e[i].w;
            q.push(make_pair(dis[e[i].v][0], e[i].v));
        }
    else
        if (dis[e[i].v][1] > dis[id][1] + e[i].w && dis[e[i].v][0] < dis[id][1] + e[i].w)
            dis[e[i].v][1] = dis[id][1] + e[i].w;
}

这样就过了90分！ 然后下载了错误数据，发现还是错在了一条边可以走多次的问题上。因为走多次的话，第一个点的次短路就不一定是0了，所以我把初始化只改成了初始化1号点的最短路。这样就过了这个题。 下面是AC代码

#include <bits/stdc++.h>
#define id tmp.second
#define di tmp.first
using namespace std;
typedef pair<int, int> PI;
const int M = 300500;
int n, r, head[M], tot, dis[M][2], vis[M];
struct EDGE{
    int v, w, nxt;
}e[M];
priority_queue<PI, vector<PI>, greater<PI> > q;
PI tmp;

void add(int x, int y, int z)
{
    e[++tot].v = y, e[tot].nxt = head[x], e[tot].w = z, head[x] = tot;
}

void Dijkstra()
{
    memset(dis, 0x4f, sizeof(dis));
    dis[1][0] = 0;
    q.push(make_pair(0, 1));
    while (!q.empty())
    {
        tmp = q.top(), q.pop();
        if (vis[id] == 2) continue;
        ++vis[id];
        for (int i = head[id]; i; i = e[i].nxt)
        {
            if (dis[e[i].v][0] > di + e[i].w)
            {
                dis[e[i].v][1] = dis[e[i].v][0], dis[e[i].v][0] = di + e[i].w;
                if (dis[e[i].v][1] > dis[id][1] + e[i].w && dis[e[i].v][0] < dis[id][1] + e[i].w)
                    dis[e[i].v][1] = dis[id][1] + e[i].w;
                if (vis[e[i].v] < 2) q.push(make_pair(dis[e[i].v][0], e[i].v));
            }
            else
                if (dis[e[i].v][1] > di + e[i].w && dis[e[i].v][0] < di + e[i].w)
                {
                    dis[e[i].v][1] = di + e[i].w;
                    if (vis[e[i].v] < 2) q.push(make_pair(dis[e[i].v][0], e[i].v));
                }
            else
                if (dis[e[i].v][1] > dis[id][1] + e[i].w && dis[e[i].v][0] < dis[id][1] + e[i].w)
                    dis[e[i].v][1] = dis[id][1] + e[i].w;
        }
    }
}

int main()
{
    int x, y, z;
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> r;
    for (int i = 1; i <= r; ++i) cin >> x >> y >> z, add(x, y, z), add(y, x, z);
    Dijkstra();
    printf("%d", dis[n][1]);
    return 0;
}