给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
Input
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。
(1Output
输出 一行有两个数, 最短距离及其花费。
 
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
C++解法,代码转自:代码转自:http://blog.csdn.net/u011538668/
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAX 1002 #define inf 999999 int map[MAX][MAX],cost[MAX][MAX]; int n; void DJ(int st,int en)//Dijkstra 传入起点和终点 { int i,j,MIN,v; int flag[MAX],dis[MAX],value[MAX]; for(i=1;i<=n;i++) { dis[i]=map[st][i]; value[i]=cost[st][i];//与一般模板相似,多加一个花费而已 } memset(flag,0,sizeof(flag)); flag[st]=1; for(i=1;i<=n;i++) { MIN=inf; for(j=1;j<=n;j++) { if(!flag[j]&&MIN>dis[j]) { v=j; MIN=dis[j]; } } if(MIN==inf)break; flag[v]=1; for(j=1;j<=n;j++) { if(!flag[j]&&map[v][j]<inf) { if(dis[j]>dis[v]+map[v][j]) { dis[j]=dis[v]+map[v][j]; value[j]=value[v]+cost[v][j];//先选好边长,同时也把对应的花费加上 } else if(dis[j]==dis[v]+map[v][j])//如果路长相等,则优先花费小的 { if(value[j]>value[v]+cost[v][j]) value[j]=value[v]+cost[v][j]; } } } } cout<<dis[en]<<" "<<value[en]<<endl;//输出到终点的最短路和花费 } int main() { int i,j,m,a,b,d,p,st,en; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)break; //memset(map,inf,sizeof(map)); //memset(cost,inf,sizeof(cost)); for(i=1;i<=n;i++) for(j=1;j<=n;j++)//初始化为最大值,用for循环更快一些 { map[i][j]=inf; cost[i][j]=inf; } while(m--) { scanf("%d%d%d%d",&a,&b,&d,&p); if(d<map[a][b]||(d==map[a][b]&&p<cost[a][b])) { map[a][b]=map[b][a]=d; cost[a][b]=cost[b][a]=p;//开两个二维数组分别记录边长和花费 } } scanf("%d%d",&st,&en); DJ(st,en); } return 0; }
C语言参考代码,转自:http://blog.csdn.net/wchyumo2009/
#include <stdio.h> #include <string.h> #define MAX 1001 #define INF 999999999 typedef struct _road { int d; int p; }road; road map[MAX][MAX]; int n, m; void init() { int i, j; for(i = 1; i <= n; i ++){ for(j = 1; j <= n; j ++){ map[i][j].d = INF; map[i][j].p = INF; } } } void dijkstra(int start, int end) { int dist[MAX]; int cost[MAX]; int min1, min2; int pre[MAX]; memset(pre, 0, sizeof(pre)); int i, j, v; for(i = 1; i <= n; i ++){ dist[i] = map[start][i].d; cost[i] = map[start][i].p; } pre[start] = 1;//循环做n-1次 for(i = 1; i < n; i ++){ min1 = INF; min2 = INF;//记录当前最短路径的顶点 for(j = 1; j <= n; j ++){ if(pre[j] == 0 && (min1 > dist[j] || (dist[j] == min1 && min2 > cost[j]))){ v = j; min1 = dist[j]; min2 = cost[j]; } } if(min1 == INF)break; pre[v] = 1;//更新 for(j = 1; j <= n; j ++){ if(pre[j] == 0){ if((dist[v] + map[v][j].d) <= dist[j] || (dist[v] + map[v][j].d == dist[j] && cost[v] + map[v][j].p < cost[j])){ dist[j] = dist[v] + map[v][j].d; cost[j] = cost[v] + map[v][j].p; } } } } printf("%d %d\n", dist[end], cost[end]); } int main() { int a, b, d, p; int i; int s, t; while(scanf("%d%d", &n, &m)!=EOF){ if(n ==0 && m == 0)break; init(); for(i = 0; i < m; i ++){ scanf("%d%d%d%d", &a, &b, &d, &p);//过滤重边 if(d < map[a][b].d || (d == map[a][b].d && p < map[a][b].p)){ map[a][b].d = map[b][a].d = d; map[a][b].p = map[b][a].p = p; } } scanf("%d%d", &s, &t); dijkstra(s, t); } return 0; }
C语言参考代码2,代码转自:http://blog.csdn.net/gubojun123/
#include<stdio.h> #define FINITY 0x7fffffff #define M 1005 int n;//图的大小 typedef struct edge_t{ int d;//距离 int p;//花费 }edge_t; edge_t m[M][M]; void dijkstra(int v0,int d[M],int p[M]){ int fin[M];//记录节点是否加入了S集合 int i,j,k,v=0,min,min_p; /**初始化*/ for(;v<n;v++){ fin[v]=0;//0表示v节点未加入S集合 d[v]=m[v0][v].d;//初始化距离记录数组 p[v]=m[v0][v].p;//初始化花费记录数组 } fin[v0]=1;//表示v0节点加入S集合 d[v0]=0;//初始化v0到v0的距离为0 /**依次找出n-1个节点加入S集合*/ for(i=1;i<n;i++){ min_p=min=FINITY; for(k=0;k<n;k++){//找最小边节点 if(!fin[k]&&d[k]<min){//!fin[k]表示k还在V-S中 v=k; min=d[k]; min_p=p[k]; } } if(min==FINITY)return; fin[v]=1;//v加入S /**修改S与V-S中各节点的距离*/ for(k=0;k<n;k++){ if(!fin[k]&&m[v][k].d!=FINITY){ if(min+m[v][k].d<d[k]){ d[k]=min+m[v][k].d; p[k]=min_p+m[v][k].p; } else if(min+m[v][k].d==d[k]&&p[k]>min_p+m[v][k].p){ p[k]=min_p+m[v][k].p; } } } } } int main(){ int i,j,t; int dis[M],pp[M]; int x,a,b,d,p,max[M],Min; while(scanf("%d%d",&n,&x)&&(n||x)){ for(i=0;i<n;i++) for(j=0;j<n;j++) m[i][j].d=m[i][j].p=FINITY; for(i=0;i<x;i++){ scanf("%d%d%d%d",&a,&b,&d,&p); if(m[a-1][b-1].d>d){ m[b-1][a-1].d=m[a-1][b-1].d=d; m[b-1][a-1].p=m[a-1][b-1].p=p; } else if(m[a-1][b-1].d==d&&m[a-1][b-1].p>p){ m[b-1][a-1].p=m[a-1][b-1].p=p; } } scanf("%d%d",&a,&b); dijkstra(a-1,dis,pp); printf("%d %d\n",dis[b-1],pp[b-1]); } }