原题链接

题解

分层图，太奥妙了
每层图都是一样的 \(d=0\) 的边建的图， \(d=1\) 就像梯子，可以去上一层走，总共有三层

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

struct node
{
    ll to, len;
};
vector<node> G[30015];
struct unit
{
    ll x, y, w;
};
struct fresh
{
    ll pos, val;
    bool operator<(const fresh &b)const
    {
        return val > b.val;
    }
};

ll dis[30015];
int main()
{
    memset(dis, 0x3f, sizeof dis);
    ll n, m;
    read(n);
    read(m);

    for(ll i = 1; i <= m; i++)
    {
        ll x, y, w, c;
        read(x);
        read(y);
        read(w);
        read(c);
        if(c)
        {
            G[x].push_back({y+n, w});
            G[x+n].push_back({y+2*n, w});
            G[y].push_back({x+n, w});
            G[y+n].push_back({x+2*n, w});
            continue;
        }

        G[x].push_back({y, w});
        G[y].push_back({x, w});
        G[x+n].push_back({y+n, w});
        G[y+n].push_back({x+n, w});
        G[x+2*n].push_back({y+2*n, w});
        G[y+2*n].push_back({x+2*n, w});
    }

    priority_queue<fresh> q;
    q.push({1, 0});
    while(q.size())
    {
        ll now = q.top().pos, val = q.top().val;
        q.pop();
        if(dis[now] <= val) continue;
        dis[now] = val;
        for(auto next: G[now])
        {
            ll to = next.to, len = next.len;
            if(dis[to] > dis[now] + len)
            {
                q.push({to, dis[now] + len});
            }
        }
    }

    // for(ll i = 1; i <= 3 * n; i++) cout << dis[i] << " ";
    write(dis[n] - min(dis[2*n], dis[3*n]));

    return 0;
}