Dijkstra

#include<iostream>
#include<cstring>
using namespace std;

const int N = 510;
int graph[N][N];
int dis[N] , vis[N];

void init()
{
    memset(dis , 0x3f , sizeof dis); # 初始时, 源点到其他点的距离都为无穷大
    memset(graph , 0x3f , sizeof graph);
}

void add(int a , int b , int c)
{
    graph[a][b] = min(graph[a][b] , c); # 在存储边时进行去重，保留更短的边
}

void dijsktra(int start , int end , int num_nodes)
{
    dis[start] = 0;

	# 迭代轮次
    for(int t = 1 ; t <= num_nodes ; t++)
    {
	    # 找到一个 未访问的 距离最小点
        int min_node = 0;
        for(int i = 1 ; i <= num_nodes ; i++)
        {
            if(!vis[i] && dis[i] < dis[min_node])
                min_node = i;
        }
        
        if(min_node == 0) return; # 没找到 停止
        if(min_node == end)  return; # 找到终点 停止
        vis[min_node] = true; # 纳入

		# 更新其他未访问节点的距离
        for(int i = 1 ; i <= num_nodes ; i++)
        {
            if(!vis[i] && dis[i] > dis[min_node] + graph[min_node][i])
            {
                dis[i] = dis[min_node] + graph[min_node][i]; 
            }
        }
    }
}

int main()
{
    init();
    int n , m; cin >> n >> m;
    while(m--)
    {
        int a , b , c; scanf("%d %d %d" , &a , &b , &c);
        add(a , b , c);
    }
    dijsktra(1 ,  n , n);
    if(dis[n] == 0x3f3f3f3f) cout << -1;
    else cout << dis[n];
}

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

const int N = 2e5;
int h[N] , e[N] , w[N] , ne[N] , idx;
int vis[N] , dis[N];
typedef pair<int, int> pos;

void init()
{
    memset(h , -1 , sizeof h);
    memset(dis , 0x3f , sizeof dis);
} 

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 end , int num_nodes)
{
	// 将起点放入优先队列
    priority_queue<pos , vector<pos> , greater<pos>> q;
    q.push({0 , start}); dis[start] = 0;
    
    // 被更新的节点会加入优先队列
    while(q.size())
    {
	    // 弹出队头 队头即当前距离最小的未被记录的点
        int node = q.top().second;
        q.pop(); 
        
	    // 因为一个节点可能被多个其他更新距离，队列中可能一个节点的多个距离
	    // 最小的距离会被首先弹出并且记录，其他距离不需要记录。
        if(vis[node]) continue; 
        // 如果记录到终点可以直接返回
        if(node == end) return;

		// 纳入这个点
        vis[node] = true;
		// 更新其他点的距离 如果其他点的距离被更新 那加入堆中
        for(int i = h[node] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(vis[j]) continue;
            if(dis[j] > dis[node] + w[i])
            {
                dis[j] = dis[node] + w[i];
                q.push({dis[j] , j});
            }
        }
    }
}

int main()
{
    init();
    int n , m; cin >> n >> m;
    while(m--)
    {
        int a , b , c; scanf("%d %d %d" , &a , &b , &c);
        add(a , b , c);
    }
    
    dijkstra(1 , n , n);
    
    if(dis[n] == 0x3f3f3f3f) cout << -1 << endl;
    else cout << dis[n];
}