过年回家

本文主要是介绍过年回家，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客网题目链接

Dijkstra算法

最短路径问题

#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std; 
const int M = 505;
const int N = 35;
int n;
int G[N][N];
int d[N];
int vis[N];
void Dijkstra(){memset(d, 0x3f, sizeof d);memset(vis, 0, sizeof vis);d[0] = 0;for(int i = 0; i <= n; i++){int u = -1;for(int j = 0; j <= n; j++){if(!vis[j] &&(u == -1 || d[u] > d[j])) u = j;}if(u == -1) return;vis[u] = 1;for(int j = 0; j <= n; j++){if(!vis[j]&&G[u][j] + d[u] < d[j]) d[j] = G[u][j] + d[u];}}
}
int main(){int m, u, v, c;while(cin>>m>>n){memset(G, 0x3f, sizeof G);for(int j = 0; j < m; j++){cin>>u>>v>>c;G[u][v] = min(G[u][v], c); //有向图 }Dijkstra();cout<<d[n]<<endl;}return 0;
}

这篇关于过年回家的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---