九度OJ 1447 最短路 1008 最短路径问题

时间：2021-12-06 16:48:59

题目地址：http://ac.jobdu.com/problem.php?pid=1447



题目描述：

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

输入：

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。

当输入为两个0时，输入结束。

输出：

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。

样例输入： 
2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0
样例输出： 
3

2

Floyd算法：

#include <stdio.h>

#include <limits.h>

void Init (int graph[101][101], int N){

    int i;

    int j;

    for (i=1; i<=N; ++i){

        for (j=1; j<=N; ++j){

            graph[i][j] = INT_MAX;

        }

    }

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

        graph[i][i] = 0;

}

void Floyd (int graph[101][101], int N){

    int i;

    int j;

    int k;

    for (k=1; k<=N; ++k){

        for (i=1; i<=N; ++i){

            for (j=1; j<=N; ++j){

                if (graph[i][k] == INT_MAX || graph[k][j] == INT_MAX)

                    continue;

                if (graph[i][j] > graph[i][k] + graph[k][j])

                    graph[i][j] =graph[i][k] + graph[k][j];

            }

        }

    }

}

int main(void){

    int N;

    int M;

    int graph[101][101];

    int start;

    int end;

    int length;

    while (scanf ("%d%d", &N, &M) != EOF && N != 0 && M != 0){

        Init (graph, N);

        while (M-- != 0){

            scanf ("%d%d%d", &start, &end, &length);

            graph[start][end] = length;

            graph[end][start] = length;

        }

        Floyd (graph, N);

        printf ("%d\n", graph[1][N]);

    }

    return 0;

}

题目地址：http://ac.jobdu.com/problem.php?pid=1008

题目描述：
给你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
来源：
2010年浙江大学计算机及软件工程研究生机试真题

Dijkstra算法：

1、邻接矩阵：

#include <stdio.h>

#include <limits.h>

#define MAXN 1001

typedef struct road{

    int len;

    int cost;

}Road;

void Init (Road graph[MAXN][MAXN], Road minlength[MAXN],int n){

    int i, j;

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

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

            graph[i][j].len = INT_MAX;

            graph[i][j].cost = INT_MAX;

        }

    }

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

        graph[i][i].len = 0;

        graph[i][i].cost = 0;

        minlength[i].len = INT_MAX;

        minlength[i].cost = INT_MAX;

    }

}

void Dijkstra (Road graph[MAXN][MAXN], Road minlength[MAXN], int N, int s, int t){

    int visited[MAXN];

    int i;

    int node;

    int reminder;

    int minlen;

    int mincost;

    int index;

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

        visited[i] = 0;

    visited[s] = 1;

    minlength[s].len = 0;

    minlength[s].cost = 0;

    reminder = N - 1;

    node = s;

    while (reminder-- != 0){

        for (i=1; i<=N; ++i){

            if (graph[node][i].len == INT_MAX || graph[node][i].len == 0)

                continue;

            else{

                if ((minlength[node].len + graph[node][i].len < minlength[i].len) ||

                    ((minlength[node].len + graph[node][i].len == minlength[i].len) &&

                    (minlength[node].cost + graph[node][i].cost < minlength[i].cost))){

                    minlength[i].len = minlength[node].len + graph[node][i].len;

                    minlength[i].cost = minlength[node].cost + graph[node][i].cost;

                }

            }

        }

        minlen = INT_MAX;

        mincost = INT_MAX;

        for (i=1; i<=N; ++i){

            if (visited[i] == 0 ){

                if (minlength[i].len < minlen || (minlength[i].len == minlen &&

                    minlength[i].cost < mincost)){

                        minlen = minlength[i].len;

                        mincost = minlength[i].cost;

                        index = i;

                }

            }

        }

        visited[index] = 1;

        node = index;

    }

}

int main(void){

    int n, m;

    int a, b, d, p;

    int s, t;

    Road graph[MAXN][MAXN];

    Road minlength[MAXN];

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

        Init (graph, minlength, n);

        while (m-- != 0){

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

            graph[a][b].len = d;

            graph[a][b].cost = p;

            graph[b][a].len = d;

            graph[b][a].cost = p;

        }

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

        Dijkstra (graph, minlength, n, s, t);

        printf ("%d %d\n", minlength[t].len, minlength[t].cost);

    }

    return 0;

}

2、邻接表：

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define MAXN 1001

typedef struct edge{

    int end;

    int len;

    int cost;

    struct edge * next;

}Edge;

typedef struct vertex{

    int start;

    struct edge * next;

}Vertex;

typedef struct road{

    int len;

    int cost;

}Road;

void Init (Vertex graph[MAXN], Road minlength[MAXN], int n){

    int i;

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

        graph[i].start = i;

        graph[i].next = NULL;

        minlength[i].len = INT_MAX;

        minlength[i].cost = INT_MAX;

    }

}

void Insert (Vertex graph[MAXN], int start, int end, int len, int cost){

    Edge * t = graph[start].next;

    Edge * pre = NULL;

    Edge * p = NULL;

    while (t != NULL && t->end != end){

        pre = t;

        t = t->next;

    }

    if (t == NULL){

        p = (Edge *)malloc(sizeof(Edge));

        p->end = end;

        p->len = len;

        p->cost = cost;

        p->next = NULL;

        if (pre != NULL)

            pre->next = p;

        else

            graph[start].next = p;

    }

    else{

        if (len < t->len || (len == t->len && cost < t->cost)){

            t->len = len;

            t->cost = cost;

        }

    }

}

void Dijkstra (Vertex graph[MAXN], Road minlength[MAXN], int N, int start, int end){

    int visited[MAXN];

    int i;

    int node;

    int reminder;

    int minlen;

    int mincost;

    int index;

    Edge * p = NULL;

    Edge * q = NULL;

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

        visited[i] = 0;

    visited[start] = 1;

    minlength[start].len = 0;

    minlength[start].cost = 0;

    reminder = N - 1;

    node = start;

    while (reminder-- != 0 && node != end){

        p = graph[node].next;

        while (p != NULL){

            if ((p->len + minlength[node].len < minlength[p->end].len) ||

                ((p->len + minlength[node].len == minlength[p->end].len) &&

                (p->cost + minlength[node].cost < minlength[p->end].cost))){

                    minlength[p->end].len = p->len + minlength[node].len;

                    minlength[p->end].cost = p->cost + minlength[node].cost;

            }

            p = p->next;

        }

        minlen = INT_MAX;

        mincost = INT_MAX;

        for (i=1; i<=N; ++i){

            if (visited[i] == 0 ){

                if (minlength[i].len < minlen || (minlength[i].len == minlen &&

                    minlength[i].cost < mincost)){

                        minlen = minlength[i].len;

                        mincost = minlength[i].cost;

                        index = i;

                }

            }

        }

        visited[index] = 1;

        node = index;

    }

}

int main(void){

    int n, m;

    int a, b, d, p;

    int s, t;

    Vertex graph[MAXN];

    Road minlength[MAXN];

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

        Init (graph, minlength, n);

        while (m-- != 0){

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

            Insert (graph, a, b, d, p);

            Insert (graph, b, a, d, p);

        }

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

        Dijkstra (graph, minlength, n, s, t);

        printf ("%d %d\n", minlength[t].len, minlength[t].cost);

    }

    return 0;

}

参考资料：* -- Floyd-Warshall算法

* -- Dijkstra算法

相关文章