对y总代码进行注释

详细题解放在笔者的csdn博客上。

https://lishizheng.blog.csdn.net/article/details/115447538

#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 200010;
const int INF = 1e6;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int f[M];// 边的类型，大路还是小路
bool st[N][1010];
int dist[N][1010];//第二维为拆点

struct Node{
    // 点，最后一条小路的长度，距离
    int x, y, v;
    // 小根堆（距离从小到大）
    bool operator<(const Node& t)const{
        return v > t.v;
    }
};

void add(int t, int a, int b, int c){
    e[idx] =b ,w[idx] = c, f[idx] = t,ne[idx] = h[a], h[a] = idx ++;
}


void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    priority_queue<Node> heap;
    heap.push({1, 0, 0});
    dist[1][0] = 0;
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        if(st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        for(int i = h[t.x]; ~i; i= ne[i]){
            int x = e[i], y = t.y;//最后一段小路的长度y
            if(f[i]){// 小路
                y += w[i]; //小路长度更新
                if(y <= 1000){ // 小路长度不会超过1000
                    if(dist[x][y] > t.v - t.y * t.y + y * y){
                        // 更新1到x点的最短路
                        dist[x][y] = t.v - t.y * t.y + y * y; 
                        if(dist[x][y] <= INF){// 加入堆
                            heap.push({x, y, dist[x][y]});
                        }
                    }
                }
            }
            else{ // 大路
                if(dist[x][0] > t.v + w[i]){
                    dist[x][0] = t.v + w[i];//权值累加
                    if(dist[x][0] <= INF)
                        heap.push({x,0, dist[x][0]});
                }
            }
        }
    }
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --){
        int t, a, b, c;
        cin >> t >> a >> b >> c;
        add(t, a, b, c), add(t, b, a, c);
    }
    dijkstra();

    int res = INF;
    // dist[n][i] 表示最后一段小路的长度为i的前提下，1到n的最短路
    // 我们通过dijkstra算法求得了合法的、最后一段是小路、但是小路长度不同的所有情况
    // 取min即可
    for(int i = 0; i <= 1000; i ++) res = min(res, dist[n][i]);
    cout << res << endl;
}