首页 > 代码库 > 1988:最短路径问题
1988:最短路径问题
时间限制：1 秒
内存限制：32 兆
特殊判题： 否
提交：72
解决： 30
标签
- 最短路径
题目描述
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
输入格式
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出
输出 一行有两个数， 最短距离及其花费。
样例输入
3 2
1 2 5 6
2 3 4 5
1 3
0 0
样例输出
9 11
DFS待会再说，先来个典型的
//最短路径问题的变异版本，本代码采用的迪杰斯特拉算法#include<stdio.h>#include<limits.h> //INT_MAX 2147483647 /* maximum (signed) int value */#define N 1001#define INF 1000000000 //int dist[N][N], price[N][N]; //使用邻接矩阵存储int set[N]; //标志是否被访问过int dis[N], pri[N]; //存放起点到各点的最短距离和花费int main() { //freopen("in.txt","r",stdin); int n, m; while(scanf("%d %d",&n,&m)!=EOF && (n||m)) { int i, j; int a, b, d, p; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { //初始化各边的距离和花费最大 dist[i][j] = dist[j][i] = INF; price[i][j] = price[j][j] = INF; } } while(m--) { scanf("%d %d %d %d",&a,&b,&d,&p); if(dist[a][b] > d) { //当有重边时，更新相关信息 dist[a][b] = dist[b][a] = d; price[a][b] = price[b][a] = p; } if(dist[a][b] == d && p<price[a][b]) { dist[a][b] = dist[b][a] = d; price[a][b] = price[b][a] = p; } } int s, t; scanf("%d %d",&s,&t); for(i=1; i<=n; i++) { //初始化起点到各点的最短距离和花费以及访问标志 dis[i] = dist[s][i]; pri[i] = price[s][i]; set[i] = 0; } set[s] = 1; //起点标志为1，表示已访问 for(i=1; i<=n; i++) { int pre_sd = INF; //存储未被访问点到起点距离的最小值 int midp; //存储未被访问点到起点距离的最小的点 for(j=1; j<=n; j++) { if(set[j]==0 && dis[j]<pre_sd) { pre_sd = dis[j]; midp = j; } } if(midp == t) //若已访问到题目给定的终点，退出循环 break; set[midp] = 1; //标志为1，表示已访问 for(j=1; j<=n; j++) { if(set[j]==0 ) { //以midp为中介点，更新各未被访问点到起点的距离和花费 if(dis[midp]+dist[midp][j] < dis[j]) { dis[j] = dis[midp]+dist[midp][j]; pri[j] = pri[midp]+price[midp][j]; } if(dis[midp]+dist[midp][j] == dis[j] && pri[j] > pri[midp]+price[midp][j]) { dis[j] = dis[midp]+dist[midp][j]; pri[j] = pri[midp]+price[midp][j]; } } } } printf("%d %d\n",dis[t],pri[t]); } return 0;}
1988:最短路径问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。