用堆优化版dijkstra写的最短路

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 50010, M = 2e5 +10;
const int INF =  0x3f3f3f3f;
typedef pair<int ,int > PII;

int n, m;
int source[6];
bool st[N];

int dist[6][N];
int h[N],e[M],ne[M],w[M],idx;

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

void dijkstra(int start, int dist[]){
    memset(dist, 0x3f,  4*N); // int 4个字节，所以大小是4*N
    memset(st,0, sizeof st);
    dist[start] = 0;
    priority_queue<PII,vector<PII>, greater<PII>> heap;

    heap.push({0,start}); // 距离，点

    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.y, distance = t.x;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

// 枚举每种拜访次序，求出最小距离
// 拜访了u个人，自己是第1个人；当前起点是source[start]，当前走过的距离是distance
int dfs(int u, int start, int distance){
    // u== 6表示：拜访完5个亲戚，此时返回最短路
    if( u == 6) return distance;
    // res存距离最短的分支
    int res = INF;
    for(int i = 1; i<=5; i ++)
        if(!st[i]){
         int next = source[i]; // 走亲戚i
         st[i] = true;
         res = min(res, dfs(u +1, i, dist[start][next] + distance));
         st[i] = false;
        }
    return res;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    source[0] = 1; 
    for(int i = 1; i <= 5; i ++) cin >> source[i];  

    while(m --){
        int x, y, t;
        cin >> x >> y >> t;
        add(x, y, t), add(y, x, t);
    }
    // 6 个点，分别求最短路
    for(int i =0; i < 6; i ++) dijkstra(source[i],dist[i]);
    /*
    1. 共有6个人，起点是自己：第1个人
    2. 当前是source[0]：佳佳
    3. 当前走过的距离是0
    */
     memset(st,0, sizeof st);
     printf("%d\n", dfs(1, 0, 0));

}