最短路径：dijkstra算法

代码语言：javascript复制

#include <iostream>
using namespace std;

#define N 510
#define INF 0x3f3f3f3

int g[N][N];
int dist[N];
bool st[N];
int n, m;


//返回值为1到n的路径长度
int dijkstra() {
	memset(dist, INF, sizeof dist);
	dist[1] = 0;//初始路径长度为0     自己到自己
	for(int i=0; i<n;   i) {
		int t = -1;
		for(int j=1; j<=n;   j) {
			if(!st[j] && (t==-1 || dist[j] < dist[t]) t = j;
		}
		st[t] = 1;
		//松弛操作
		for(int j=1; j<=n;   j) dist[j] = min(dist[j], dist[t]  g[t][j]);
	}
	if(dist[n] == INF) return -1;
	else return dist[n];
}


int main() {
    cin >> n >> m;
    for(int i=1; i<=n;   i) {
        for(int j=1; j<=n;   j) {
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }
    
    while(m --) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

dijkstra

0 人点赞