本文共 2118 字，大约阅读时间需要 7 分钟。

分析

本题要求从1点出发，找到一条到达终点n的最短路。(单源最短路)
设type为路的种类，当路的type为0是代表是大路，此外所有的type都是代表小路。
因为题目保证答案不会超过1e6，所以type*type<=1e6，即type<=1000

C++ 代码

#include<bits/stdc++.h>using namespace std;const int N = 510,M = 2e5+10;int h[N],e[M],T[M],w[M],ne[M],idx;      //T用来表示路的种类int n,m,dist[N][1010];  //dist[x][y]：到x点，类型为y的最短距离(<=1000)bool st[N][1010];   //st[x][y]：到x点，类型为y的路是否遍历过(<=1000)void add(int a,int b,int c,int type){    e[idx]=b,w[idx]=c,T[idx]=type,ne[idx]=h[a],h[a]=idx++;}struct node{    int x,type,w;   //x点为当前点x，type为路的种类        bool operator<(const node &p)const{        return w>p.w;       //当路的类型为大路时，它的w值通常会比小路的w大很多，所以优先选取大路来走    }};void spfa(){    memset(dist,0x3f,sizeof dist);        priority_queue<node> q; //用一个优先队列存储所有节点    q.push({1,0,0});    //1:1号点，0:种类为0，到起点1的距离为0    dist[1][0]=0;        while(q.size())    {        auto t=q.top();        q.pop();        if(st[t.x][t.type]) continue;   //此状态遍历过，直接跳过        st[t.x][t.type]=1;        for(int i=h[t.x];~i;i=ne[i])    //枚举所有出边        {            int j=e[i];            if(!T[i])       //如果type为0，说明为大路，按照平常求最短路逻辑进行计算即可            {                if(dist[j][0]>dist[t.x][t.type]+w[i])                {                    dist[j][0]=dist[t.x][t.type]+w[i];                    if(dist[j][0] <= 1e6)   //答案保证不超过1e6                        q.push({j,0,dist[j][0]});                }            }            else if(t.type+w[i]<=1000){     //路的种类为小路，且总和不超过1000                int tt=t.type+w[i];     //新的小路的种类为tt                if(dist[j][tt]>dist[t.x][t.type]-t.type*t.type+tt*tt)                 {                    dist[j][tt]=dist[t.x][t.type]-t.type*t.type+tt*tt;                    if(dist[j][tt]<=1e6)    //答案保证不超过1e6                        q.push({j,tt,dist[j][tt]});                }            }        }    }}int main(){    memset(h,-1,sizeof h);    cin>>n>>m;    int type,a,b,c;    for(int i=0;i<m;i++)    {        cin>>type>>a>>b>>c;        add(a,b,c,type),add(b,a,c,type);    }        spfa();        int res = 1e6;    for (int i=0;i<=1000;i++ )      {        res = min(res, dist[n][i]); //起点达到终点n，状态为i的最短距离    }    printf("%d\n", res);        return 0;}