迪杰斯特拉算法 --O(nlogn)
- #include"iostream"
- #include"cstring"
- #include"cstdio"
- using namespace std;
- const int inf = 0x3f3f3f3f;
- typedef long long LL;
- int map[105][105];
- int ans[105], n, m;
- bool flag[105];
- void dij() {
- for(int i = 2; i <= n; i++)
- ans[i] = map[1][i];
- ans[1] = 0;
- memset(flag, true, sizeof(flag));
- flag[1] = false;
- for(int i = 2; i <n; i++) {
- int v, mn = inf;
- for(int j = 1; j <= n; j++)
- if(ans[j] < mn && flag[j]) {
- mn = ans[j];
- v = j;
- }
- for(int j = 1; j <= n; j++)
- if(ans[v] + map[v][j] < ans[j])
- ans[j] = ans[v] + map[v][j];
- flag[v] = false;
- }
- }
- int main() {
- int a, b, c;
- while(scanf("%d%d", &n, &m) && (n || m)) {
- memset(map, inf, sizeof(map));
- while(m--) {
- scanf("%d%d%d", &a, &b, &c);
- if(map[a][b]> c)
- map[a][b] = map[b][a] = c;
- }
- dij();
- printf("%d\n", ans[n]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2775089.html