一遍不行就两遍

口胡得来终觉浅, 觉知此题要写明

懵逼的 题目

传送至 luogu

扯淡的 题解

emmmm偶然翻luogu发现的学长给我的题…然后就毫不犹豫的做啦…
大体思路就是从终点两遍最短路, 标记最短路

然后对每一条边

  • 有一个GPS以它为最短路的一部分时 设其边权为1
  • 有两个GPS以它为最短路的一部分时 设其边权为0
  • 没有GPS以它为最短路的一部分时 设边权为2

然后再(从起点)跑一边最短路… dis[n] 就是答案…

然后因为已经有了思路就写的飞快…30min左右写完惹(梦回巅峰!)…
然后没过样例
调了30min+…手玩了一遍样例…发现…诶诶诶样例怎么是错的啊…???
回去看看题目…发现翻译没有翻译出来 directional roads 所以这是个有向图啊喂!
然后…机房就快锁门惹…
第二天…交上去…T飞辣… 50…
发现是不是这题卡SPFA啊…
改成dijk…交上去T惹一个点…然后各种卡时…无果
发现标记某条边是否是最短路的一部分时写的非常诡异…可能被卡成 o(n ^ 2)
改完交上去…终于过惹…

我是不是傻啊QAQ

沙茶的 代码

诶诶诶写代码的时候脑子抽惹…写了三遍建图 + 最短路…
有空按照高级点的写法重写一遍

// T1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (10000 + 5)
#define MAXM (50000 + 5)
#define INF (0x7ffffff)
const int s = 1; 
int t = 1; 
using namespace std;

struct edg
{
    int from;
    int to;
    int next;
    int cost;
    bool atp;
    bool atq;
}bp[MAXM << 1], bq[MAXM << 1], ba[MAXM << 1];
int cntp = 0, cntq = 0, cnta = 0;
int gp[MAXN], gq[MAXN], ga[MAXN];

int n;
int m;
int disp[MAXN], disq[MAXN], disa[MAXN];

struct cmpp
{
    bool operator () (int x, int y)
    {
        return disp[x] > disp[y];
    }
};

struct cmpq
{
    bool operator () (int x, int y)
    {
        return disq[x] > disq[y];
    }
};

struct cmpa
{
    bool operator () (int x, int y)
    {
        return disa[x] > disa[y];
    }
};

void init();
void inita();
void adnp(int, int, int);
void adnq(int, int, int);
void adna(int, int, int);

void dijkp(const int);
void dijkq(const int);
void dijka(const int);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    init();
    dijkp(n);
    dijkq(n);
    inita();
    dijka(1);
    cout << disa[n];
    return 0;
}

void init()
{
    memset(disp, 0x7f, sizeof(disp));
    memset(disq, 0x7f, sizeof(disq));
    memset(disa, 0x7f, sizeof(disa));
    cin >> n >> m;
    t = n;
    int srx, sry, srzp, srzq;
    for (int i = 1; i <= m; i++)
    {
        cin >> srx >> sry >> srzp >> srzq;
        //adnp(srx, sry, srzp);
        adnp(sry, srx, srzp);
        //adnq(srx, sry, srzq);
        adnq(sry, srx, srzq);
        adna(srx, sry, 2);
        //adna(sry, srx, 2);
    }
}

void dijkp(const int startDash)// 反向最短路: GPSp's way
{
    bool v[MAXN];
    int pre[MAXN];
    memset(v, false, sizeof(v));
    memset(pre, 0, sizeof(pre));
    bp[0].from = startDash;
    priority_queue<int, vector<int>, cmpp> q;
    v[startDash] = true;
    disp[startDash] = 0;
    q.push(startDash);
    while (!q.empty())
    {
        int dq = q.top();    q.pop();
        v[dq] = true;
        for (int i = gp[dq]; i; i = bp[i].next)
        {
            if (disp[bp[i].to] > disp[dq] + bp[i].cost)
            {
                disp[bp[i].to] = disp[dq] + bp[i].cost;
                pre[bp[i].to] = i;
                if (!v[bp[i].to])
                    q.push(bp[i].to);
            }
        }
    }
}

void dijkq(const int startDash)// 反向最短路: GPSq's way
{
    bool v[MAXN];
    int pre[MAXN];
    memset(v, false, sizeof(v));
    memset(pre, 0, sizeof(pre));
    bq[0].from = startDash;
    priority_queue<int, vector<int>, cmpq> q;
    v[startDash] = true;
    disq[startDash] = 0;
    q.push(startDash);
    while (!q.empty())
    {
        int dq = q.top();    q.pop();
        v[dq] = true;
        for (int i = gq[dq]; i; i = bq[i].next)
        {
            if (disq[bq[i].to] > disq[dq] + bq[i].cost)
            {
                disq[bq[i].to] = disq[dq] + bq[i].cost;
                pre[bq[i].to] = i;
                if (!v[bq[i].to])
                    q.push(bq[i].to);
            }
        }
    }
}

void dijka(const int startDash)// 正向最短路: ans
{
    bool v[MAXN];
    int pre[MAXN];
    memset(v, false, sizeof(v));
    priority_queue<int, vector<int>, cmpa> q;
    v[startDash] = true;
    disa[startDash] = 0;
    q.push(startDash);
    while (!q.empty())
    {
        int dq = q.top();    q.pop();
        v[dq] = true;
        for (int i = ga[dq]; i; i = ba[i].next)
        {
            if (disa[ba[i].to] > disa[dq] + ba[i].cost)
            {
                disa[ba[i].to] = disa[dq] + ba[i].cost;
                pre[ba[i].to] = i;
                if (!v[ba[i].to])
                    q.push(ba[i].to);
            }
        }
    }
}


void adnp(int from, int to, int cost)
{
    bp[++cntp].next = gp[from];
    bp[cntp].from = from;
    bp[cntp].to = to;
    bp[cntp].cost = cost;
    gp[from] = cntp;
}

void adnq(int from, int to, int cost)
{
    bq[++cntq].next = gq[from];
    bq[cntq].from = from;
    bq[cntq].to = to;
    bq[cntq].cost = cost;
    gq[from] = cntq;
}

void adna(int from, int to, int cost)
{
    ba[++cnta].next = ga[from];
    ba[cnta].from = from;
    ba[cnta].to = to;
    ba[cnta].cost = cost;
    ba[cnta].atp = false;
    ba[cnta].atp = false;
    ga[from] = cnta;
}

void inita()
{
    bool v[MAXN];
    queue<int> q;

    memset(v, false, sizeof(v));
    q.push(t);

    while (!q.empty())// GPS p
    {
        int dq = q.front();    q.pop();
        v[dq] = true;
        for (int i = gp[dq]; i; i = bp[i].next)
        {
            if (disp[dq] + bp[i].cost == disp[bp[i].to] && !v[bp[i].to])
            {
                ba[i].atp = true;
                q.push(bp[i].to);
            }
        }
    }

    memset(v, false, sizeof(v));
    q.push(t);

    while (!q.empty())// GPS q
    {
        int dq = q.front();    q.pop();
        v[dq] = true;
        for (int i = gq[dq]; i; i = bq[i].next)
        {
            if (disq[dq] + bq[i].cost == disq[bq[i].to] && !v[bq[i].to])
            {
                ba[i].atq = true;
                q.push(bq[i].to);
            }
        }
    }

    for (int i = 1; i <= m; i++)
    {
        if (ba[i].atp)
            ba[i].cost--;
        if (ba[i].atq)
            ba[i].cost--;
    }
}

/*
5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
*/

By 文化课爆炸的 Cansult