dijkstra解题代码

刺骨的言语ヽ痛彻心扉 2022-04-12 12:43 104阅读 0赞

#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;
    }