Pro4_WA

原始文件为 CPP 代码，本文是转换后的 Markdown 文件。

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

const int maxn = 505;
const int INF = 1000005;
const int INF_SQ = 1001;

struct Edge
{
    int type, from, to, weight;
    Edge(int y, int f, int t, int w) : type(y), from(f), to(t), weight(w) {}
    bool operator<(const Edge& e2) { return weight < e2.weight; }
};

struct HeapNode
{
    int value, pos;
    HeapNode(int p,int v):pos(p),value(v){}
    bool operator < (const HeapNode& other) const
    {
        return value > other.value;
    }
};

struct Dijkstra
{
    vector<int> adjG[maxn];
    vector<Edge> edges;

    int n;
    bool visit[maxn];
    int easyedge[maxn];
    int hardedge[maxn];

    void init(int n)
    {
        this->n = n;
        for(int i = 0; i <= n; ++i) adjG[i].clear();    
        for(int i = 0; i <= n; ++i) easyedge[i] = INF;
        for(int i = 0; i <= n; ++i) hardedge[i] = INF;
        memset(visit, false, sizeof(visit));  
        edges.clear();
    }

    void add_edge(int type, int from,int to,int weight)
    {
        adjG[from].push_back(edges.size());
        edges.push_back( Edge{type,from,to,weight} );
    }

    int get_shortest(int node)
    {
        return min(hardedge[node], easyedge[node]);
    }

    void dijkstra(int root) 
    {  
        priority_queue<HeapNode> Q;     

        visit[root] = false; easyedge[root] = 0; hardedge[root] = 0;
        Q.push((HeapNode){root, 0});  
        while(!Q.empty()) 
        {    
            HeapNode x = Q.top(); Q.pop();    
            int u = x.pos;

            if(u == n) break; if(visit[u]) continue;   
            visit[u] = true;    

            // printf("dijkstra(%d)\n", u);
            for(int i = 0; i < adjG[u].size(); ++i)
            {
                Edge& e = edges[ adjG[u][i] ]; 
                int v = e.to; int type = e.type; if(visit[v]) continue;
                if(type)
                {
                    // 走小路，只能从大路转到小路
                    if(hardedge[v] > easyedge[u] + e.weight)
                    {
                        hardedge[v] = min(hardedge[v], easyedge[u] + e.weight);
                        Q.push( HeapNode {v, min(hardedge[v], easyedge[v])} );
                    }
                }else
                {
                    // 走大路，可以从小路转到大路，也可以从大路转到大路
                    if(easyedge[v] > min(hardedge[u]+e.weight, easyedge[u]+e.weight))
                    {
                        easyedge[v] = min(hardedge[u] + e.weight, easyedge[u] + e.weight);
                        Q.push( HeapNode {v, min(hardedge[v], easyedge[v])} );
                    }
                }
            }
            // for(int i = 1; i <= n; ++i)
            // {
            //     printf("%d: hard=%d, easy=%d\n", i, hardedge[i], easyedge[i]);
            // }
        } 
    }
};

int hardedge[maxn][maxn];
void floyd(int n)
{
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                hardedge[i][j] = min(hardedge[i][j], hardedge[i][k]+hardedge[k][j]);
}


int main()
{
    for(int i = 0; i < maxn; ++i)
        for(int j = 0; j < maxn; ++j) hardedge[i][j] = INF;
    for(int i = 0; i < maxn; ++i) hardedge[i][i] = 0;

    // freopen("in2.txt", "r", stdin);
    int n, m; scanf("%d%d", &n, &m);

    Dijkstra d{}; d.init(n);
    for(int i = 0; i < m; ++i)
    {
        int type, from, to, weight;
        scanf("%d%d%d%d", &type, &from, &to, &weight);
        if(type)
        {
            hardedge[from][to] = hardedge[to][from] = weight;
        }else
        {
            d.add_edge(0, from, to, weight);
            d.add_edge(0, to, from, weight);
        }
    }

    floyd(n);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(hardedge[i][j] > INF_SQ) continue;

            int weight = hardedge[i][j] * hardedge[i][j];
            if(weight > 0) d.add_edge(1, i, j, weight);
        }
    }
    d.dijkstra(1);
    cout << d.get_shortest(n) << endl;

    return 0;
}