7-9 旅游规划 (25 分)【Floyd】【Dijkstra】

青旅半醒 2022-10-28 00:58 138阅读 0赞

## Floyd算法 ##

Floyd是求多源最短路径（任意两个顶点之间的最短路径）的算法，因为这道题的起点和终点都已确定，所以没有必要在进行三层循环，直接将i确定为s,求s到其它顶点的最短路径。

#include <iostream>
    using namespace std;
    int map[505][505], cost[505][505];
    int main() {
        
    	int n, m, s, d;
    	cin >> n >> m >> s >> d;
    	for(int i = 0; i < n; i++) {
        
    		for(int j = 0; j < n; j++) {
        
    			map[i][j] = 10000;
    			cost[i][j] = 10000;
    		}
    	}
    	for(int i = 0; i < m; i++) {
        
    		int a, b, c, d;
    		cin >> a >> b >> c >> d;
    		map[a][b] = map[b][a] = c;
    		cost[a][b] = cost[b][a] = d;
    	}
    	/*
    	for(int k = 0; k < n; k++) {
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(map[i][j] > map[i][k]+map[k][j] || (map[i][j]==map[i][k]+map[k][j]&&cost[i][j]>cost[i][k]+cost[k][j])) {
    					cost[i][j] = cost[i][k]+cost[k][j];
    					map[i][j] = map[i][k]+map[k][j];
    				}
    			}
    		}
    	}
    	*/
    	for(int k = 0; k < n; k++) {
        
    		for(int j = 0; j < n; j++) {
        
    			if(map[s][j] > map[s][k]+map[k][j] || (map[s][j]==map[s][k]+map[k][j]&&cost[s][j]>cost[s][k]+cost[k][j])) {
        
    				cost[s][j] = cost[s][k]+cost[k][j];
    				map[s][j] = map[s][k]+map[k][j];
    			}
    		}
    	}
    	cout << map[s][d] << " " << cost[s][d];
    }

## Dijkstra算法 ##

#include <iostream>
    using namespace std;
    int map[505][505], cost[505][505], vis[505], dis[505];
    int main() {
        
    	int n, m, s, d;
    	cin >> n >> m >> s >> d;
    	for(int i = 0; i < n; i++) {
             //初始化
    		for(int j = 0; j < n; j++) {
        
    			map[i][j] = 10000;
    			cost[i][j] = 10000;
    		}
    		map[i][i] = 0;
    	}
    	for(int i = 0; i < m; i++) {
        
    		int a, b, c, d;
    		cin >> a >> b >> c >> d;
    		map[a][b] = map[b][a] = c;
    		cost[a][b] = cost[b][a] = d;
    	}
    	vis[505] = {
        0};
    	for(int i = 0; i < n; i++) {
        
    		dis[i] = map[s][i];
    	}
    	vis[s] = 1;
    	int sum = 0;
    	for(int t = 0; t < n; t++) {
        
    		int minx = 10000, tmp;
    		for(int i = 0; i < n; i++) {
        
    			if(!vis[i] && dis[i] < minx) {
        
    				tmp = i;
    				minx = dis[i];
    			}
    		}
    		vis[tmp] = 1;
    		for(int i = 0; i < n; i++) {
        
    			if(dis[i] > map[tmp][i]+dis[tmp] || (dis[i]==map[tmp][i]+dis[tmp]&&cost[s][tmp]+cost[tmp][i]<cost[s][i])) {
        
    				dis[i] = map[tmp][i]+dis[tmp];
    				cost[s][i] = cost[s][tmp]+cost[tmp][i];
    			}
    		}
    	}
    	cout << dis[d] << " " << cost[s][d];
    }

**题目描述**  
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

**输入格式:**  
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

**输出格式:**  
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

**输入样例:**

4 5 0 3
    0 1 1 20
    1 3 2 30
    0 3 4 10
    0 2 2 20
    2 3 1 20

**输出样例:**

3 40