/*
    Author: Sean_xzx
    Right Output! & Accepted!
本题核心：
1.
本题步骤：
1.
*/
#include <bits/stdc++.h>

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, long long>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int mod = ;

template <typename T> inline void rd(T &x){
    x = 0; bool f = true; char ch = getchar();
    while(ch < '0' || ch > '9'){ f = ((ch == '-') ? false : true); ch = getchar();}
    while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
    if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}

using namespace std;

const int N = 1.5e5 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool vis[N];

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

int Dij(){
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 因为对到源点边权从小到大排序，但我们又想知道这个点是哪一个所以用heap greater PII
    mms(dist, 0x3f); dist[1] = 0;
    heap.push(mp(0, 1));

    while(heap.size()){
        auto temp = heap.top(); heap.pop();
        int t = temp.se;
        if(vis[t]) continue;
        vis[t] = true;

        for(int i = h[t]; i; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                heap.push(mp(dist[j], j));
            }
        }
    }
    if(dist[n] == inf) return -1;
    else return dist[n];
}

int main(){
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    rd(n, m);
    for(int i = 1; i <= m; i++){
        int x, y, w;
        rd(x, y, w);
        add(x, y, w);
    }
    prf("%d\n", Dij());
    return 0;
}

1.优先队列优化的是$O(mlogm)$还是$O(mlogn)$
2.如果是$mlogm$,岂不是跟点数没有关系\

using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool vis[N];
void init(){
    mms(g, 0x3f);
}
int Dij(){
    mms(dist, 0x3f);
    dist[1] = 0;

    for(int i = 1; i <= n; i++){
        int t = -1;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && (t == -1 || (dist[t] > dist[j]))) t = j;
        }
        vis[t] = true;
        for(int j = 1; j <= n; j++){
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    if(dist[n] == inf) return -1;
    else return dist[n];
}
int main(){
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    init();
    rd(n, m);
    for(int i = 1; i <= m; i++){
        int x, y, w;
        rd(x, y, w);
        g[x][y] = min(g[x][y], w);
    }
    prf("%d\n",Dij());
    return 0;
}

3.稠密图的朴素邻接矩阵的复杂度为$O(n(n + n)) \rightarrow O(n^2)$,但如果换为邻接表就变为了$O(n^2 + m)$,稠密图是不是比较$m$与$n^2$的大小来选择邻接表，和邻接矩阵\

这三个问题，谢谢了