[数据结构与算法]【acwing】1129. 热浪*(dijkstra模板题）

穿越隧道

朴素和优化的dijkstra都可。
目前，只有朴素，后续优化待补

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 2510;
int g[N][N];
int a,b;
int n;
int dis[N];
bool vis[N];
int t,c,s,e;
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s] = 0;
    // cout << "dis[0]" << dis[s] << endl;
    // cout <<"t = " << t << endl;
    for(int i = 1; i <= t; i++){
        int tt = -1;
        for(int j = 1; j <= t; j++){
            if(!vis[j] && (tt == -1 || dis[tt] > dis[j])){
                tt = j;
            }
        }
        vis[tt] = true;
        for(int j = 1; j <= t; j++){
            dis[j] = min(dis[j],dis[tt] + g[tt][j]);
        }
    }
    // return dis[ed];
}
int main(){
    scanf("%d%d%d%d",&t,&n,&s,&e);//t相当于n个结点，n相当于m条无向边。
    //因为t和n与原来的n和m没联系上，导致怀疑模板写错了。。还是需要多背模板。
    memset(g,0x3f,sizeof(g));
    // int u = n;
    while(n--){
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = g[b][a] = min(g[a][b],c);
        g[b][a] = min(g[b][a],c);//这样也行，但没并列简洁
    }
    //调试
    // for(int i = 1; i <= 20; i++){
    //     for(int j = 1; j <= 20; j++){
    //         cout << g[i][j] <<" ";
    //     }
    //     puts("");
    // }

    dijkstra();
    printf("%d\n",dis[e]);
    return 0;
}