Pro4

原始文件为 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, dist;
    Edge(int y, int f, int t, int w) : type(y), from(f), to(t), dist(w) {}
    bool operator<(const Edge& e2) { return dist < e2.dist; }
};

bool inq[maxn]; 
int hardway[maxn];
int easyway[maxn];
vector<int> G[maxn];
vector<Edge> edges;

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

void bellman_ford(int n)
{
    queue<int> Q;
    memset(hardway, INF, sizeof(hardway));
    memset(easyway, INF, sizeof(easyway));
    memset(inq, false, sizeof(inq));

    easyway[1] = 0; hardway[1] = 0; 
    inq[1] = true; Q.push(1);

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        inq[u] = false;

        for(int i = 0; i < G[u].size(); ++i)
        {
            Edge& e = edges[G[u][i]];
            if(e.type)
            {
                // 小路，只能大路到小路
                if(hardway[e.to] > easyway[u] + e.dist)
                {
                    hardway[e.to] = easyway[u] + e.dist;
                    if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; }
                }
            }else
            {
                if(easyway[u] > hardway[u])
                {
                    if(easyway[e.to] > hardway[u] + e.dist)
                    {
                        easyway[e.to] = hardway[u] + e.dist;
                        if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; }
                    }
                }else
                {
                    if(easyway[e.to] > easyway[u] + e.dist)
                    {
                        easyway[e.to] = easyway[u] + e.dist;
                        if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; }
                    }
                }
            }
        }
    }
}

int hardedge[maxn][maxn];
void floyd(int n)
{
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            for(int k=1; k<=n; k++)
                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);

    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
        {
            add_edge(0, from, to, weight);
            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) add_edge(1, i, j, weight);
        }
    }

    bellman_ford(n);
    cout << min(hardway[n], easyway[n]) << endl;

    return 0;
}