九度OJ 1008：最短路径问题（最短路）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：8064

解决：2685

题目描述：: 给你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)

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

样例输入：

样例输出：

9 11

来源：: 2010年浙江大学计算机及软件工程研究生机试真题

思路：

典型最短路径问题，通常有两种方法：Dijkstra和floyd算法。我比较喜欢用前一种。

最短路径算法的介绍可参见博客：http://blog.csdn.net/damenhanter/article/details/24771913

本题除了最短路径，还加上了花费，其实原理一样的。

代码：

#include <stdio.h>

#define N 1000

#define INF 1000000000

int D[N][N], P[N][N];

int visit[N], dis[N], pay[N];

void init(int n)

{

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

    {

        visit[i] = 0;

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

        {

            D[i][j] = INF;

            P[i][j] = INF;

        }

    }

}

void printdis(int n)

{

    int i;

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

        printf("%d ", dis[i]);

    printf("%d\n", dis[i]);

}

void dijkstra(int s, int n)

{

    int i, j;

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

    {

        dis[i] = D[s][i];

        pay[i] = P[s][i];

    }

    dis[s] = 0;

    pay[s] = 0;

    visit[s] = 1;

    //printdis(n);

    int mind, minp;

    int k;

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

    {

        mind = INF;

        minp = INF;

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

        {

            if ( !visit[j] && (dis[j]<mind

                || dis[j]==mind && pay[j]<minp) )

            {

                mind = dis[j];

                minp = pay[j];

                k = j;

            }

        }

        visit[k] = 1;

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

        {

            if ( !visit[j] && (dis[k]+D[k][j] < dis[j]

                || dis[k]+D[k][j] == dis[j] && pay[k]+P[k][j] < pay[j]) )

            {

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

                pay[j] = pay[k]+P[k][j];

            }

        }

    }

    //printdis(n);

}

int main(void)

{

    int n, m, i;

    int a, b, d, p;

    int s, t;

    while (scanf("%d%d", &n, &m) != EOF)

    {

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

            break;

        init(n);

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

        {

            scanf("%d%d%d%d", &a, &b, &d, &p);

            D[a-1][b-1] = D[b-1][a-1] = d;

            P[a-1][b-1] = P[b-1][a-1] = p;

        }

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

        dijkstra(s-1, n);

        printf("%d %d\n", dis[t-1], pay[t-1]);

    }

    return 0;

}

/**************************************************************

    Problem: 1008

    User: liangrx06

    Language: C

    Result: Accepted

    Time:20 ms

    Memory:8736 kb

****************************************************************/

最短

九度OJ 1008：最短路径问题 （最短路）

九度OJ 1008：最短路径问题（最短路）