【洛谷】P1576 最小花费

骑猪看日落 2022-09-09 09:12 172阅读 0赞

# 前言 #

*  文章来源：CSDN@LawsonAbs
 *  合理时间：12min

--------------------

# 题目 #

[题目链接][Link 1]

# 分析 #

这题可以看做是dijkstra算法的变形。朴素的dijkstra算法就是求单源最短路径，但是这里给出的不是路径的权重，而是将权重看成一个比例，我们需要用这个比例，间接的结算出到下一跳的权重。

*  dijkstra算法

# 代码 #

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxN = 2001;
    double gra[maxN][maxN] ;
    double dis[maxN] ;//dis[i] 表示source -> i点的距离
    int n,m;
    const int INF = 1e9;
    bool vis[maxN];
    
    //source -> destination
    void dijkstra(){ 
    	int cnt = n;// 初始化 
    	while(cnt--){ 
    		int cur_dis = INF,cur_node;
    		for (int i = 1;i<=n;i++){ 
    			if(!vis[i]){ //如果该节点未访问 
    				if(dis[i] < cur_dis){ //找出当前最小的距离 
    					cur_dis = dis[i];
    					cur_node = i; 	
    				}			
    			}
    		} 
    		vis[cur_node] = true;//表示已经确认了 
    		//使用cur_node作为中间节点，迭代更新距离 
    		for(int i = 1;i<=n;i++){ 
    			if(gra[cur_node][i]!=1){ //如果两者之间有边 
    				double temp =  (dis[cur_node]/(1.0-gra[cur_node][i])); 
    				if(!vis[i] && dis[i] > temp){ 
    					dis[i] = temp;
    				}
    			}
    		}
    	} 
    }
    
    int main(){ 
    	cin >> n >> m;
    	int a,b,c;
    	double z;
    	fill(dis,dis+maxN,INF);//初始化为最大值 
    	fill(vis,vis+maxN,false);
    	fill(gra[0],gra[0]+maxN*maxN,1);//初始化为1 
    	for(int i = 0;i< m;i++){ 
    		cin >> a >> b >> c;
    		z = c * 0.01; 
    		gra[a][b] = z; // 权重 
    		gra[b][a] = z;
    	}
    	int s,d;//源点，终点 
    	cin >> s >> d;
    	dis[s] = 100; 
    	dijkstra(); 
    	printf("%0.8f",dis[d]);  
    }
    /* 3 2 1 2 1 1 3 3 1 3 */

# 坑点 #

*  dijkstra算法外部有一个for循环，用于让所有的节点都被访问到
 *  记得初始化`gra[][]` 图。

[Link 1]: https://www.luogu.com.cn/problem/P1576