dijkstra解题代码

#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <ctime>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <stack>
using namespace std;

#define vi vector<int>
#define mod 1000000007
#define inf 1000000007
#define ll long long
#define DBG(x) cerr<< (#x) <<"="<<x<<"\n";

template <class T> void add(int &a,T b){a=(a+b)%mod;}
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

//基于数组的找当前最近节点
int getNext(vector<int>& visited,vector<int>& path) {
	int minv = inf,index = -1;
	//从数组当中找出没有访问的节点的最小值得下标返回
	for(int i=1;i<path.size();++i) {
		if(path[i]<minv&&visited[i]==0) {
			minv = path[i];
			index = i;
		}
	}
	return index;
}
//基于数组的dijkstra算法 解决非负权值的段元最短路径
void Dijkstra(vector<vector<int>>& G,vector<int>& path,int x) {
	vector<int> visited(G.size(),0);

	for(int i=1;i<G.size();++i) {
		//获取下一个最邻近节点
		int next = getNext(visited,path);
		//如果没有说明已经结束了
		if(next==-1) return;
		//将当前节点标识已经访问过
		visited[next] = 1;
		//使用当前节点的所有的边去松弛所有的距离path
		for(int j=1;j<G.size();++j) {
			if(G[next][j]) {
				if(path[next]+1<path[j])
					path[j] = path[next] + 1;
			}
		}
	}
	return;
}


int main() {
	int N,M,W;
	cin >> N >> M >> W;
	vector<vector<int>> G(N+1,vector<int>(N+1,0));
	//构建图 使用邻接矩阵的方式 将问题简化成无向无权图
	for(int i=0;i<M;++i) {
		int a,b,c;
		cin >> a >> b >> c;
		if(c>=W) {
			G[a][b] = 1;
			G[b][a] = 1;
		}
	}

	vector<int> path(N+1,inf);
	path[1] = 0;
	Dijkstra(G,path,1);
	if(path[N]==inf)
		cout << -1 << endl;
	else
		cout << path[N] << endl;
    return 0;
}