Problem Description

给你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时输入结束。

(1<n<=1000, 0<m<100000, s != t)

 

Output

输出 一行有两个数， 最短距离及其花费。

 

Sample Input

3 2

1 2 5 6

2 3 4 5

1 3

0 0

 

Sample Output

9 11

 

Source

代码例如以下：

#include <cstdio>

#include <iostream>

#include <algorithm>

#define MAXN 1017

#define INF 0x3fffffff

using namespace std;

int mat[MAXN][MAXN];

int cost[MAXN][MAXN];

int n,m;//n为结点数。m为道路数

int MONEY[MAXN];

int dijkstra (int s,int f)

{

	//s为起点。 f：为终点

	int dis[MAXN];//记录到随意点的最短距离

	int mark[MAXN];//记录被选中的结点

	int i, j, k;

    for(i = 1; i <= n; i++)

    {

		mark[i] = 0;//初始化全部结点。每一个结点都没有被选中

        dis[i] = mat[s][i];

		MONEY[i] = cost[s][i];

    }

    mark[s] = 1;//start结点被选中

    dis[s] = 0;//将start结点的的距离设置为0

    int min;//设置最短的距离。

    for(i = 1; i <= n; i++)

    {

		k = 1;//赋初值非常重要

        min = INF;

        for(j = 1; j <= n;j++)

        {

            if(mark[j] == 0 && dis[j] < min)//未被选中的结点中，距离最短的被选中

            {

                min = dis[j] ;

                k = j;

            }

        }

        mark[k] = 1;//标记为被选中

        for(j = 1; j <= n; j++)

        {

			if(!mark[j] && dis[j]>dis[k]+mat[k][j])//改动剩余结点的最短距离

			{

				dis[j] = dis[k] + mat[k][j];

				MONEY[j]=MONEY[k]+cost[k][j];

			}

			else if(!mark[j] && dis[j]==dis[k]+mat[k][j])

			{

				if(MONEY[j] > MONEY[k]+cost[k][j])

					MONEY[j] = MONEY[k]+cost[k][j];

			}

		}

	}

	return dis[f];

} 

void init()

{

	for(int i = 1; i <= n; i++)

	{

		for(int j = 1; j <= n; j++)

		{

			cost[i][j] = INF;

			if(i == j)

				mat[i][j] = 0;

			else

				mat[i][j] = INF;

		}

	}

}

int main()

{

	int i,j;

	int a,b,dis,mon;

	while(scanf("%d %d",&n,&m))

	{

		if(n == 0 && m == 0)

			break;

		init();

		for(i = 1; i <= m; i++)

		{

			scanf("%d %d %d %d",&a,&b,&dis,&mon);

			if(dis < mat[a][b])

			{

				mat[a][b] = mat[b][a] = dis;

				cost[a][b] = cost[b][a]= mon;

			}

			if(dis == mat[a][b])

			{

				if(mon < cost[a][b])

					cost[a][b] = cost[b][a] = mon;

			}

		}

		int s, e;

		scanf("%d%d",&s,&e);

		int ans = dijkstra(s, e);

		printf("%d %d\n",ans,MONEY[e]);

	}

	return 0;

}

版权声明：本文博客原创文章，博客，未经同意，不得转载。