首页 > 代码库 > 九度 题目1008：最短路径问题

九度 题目1008：最短路径问题

2024-08-06 03:18:51   213人阅读

最短路径问题，首先想到了贪心算法实现的dijkstra算法；这道题我用了链表的存储方式，其实用邻接矩阵也可以，主要为了练手，并且链表比矩阵要节约空间；

题目描述：
给你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
AC代码如下(主要运用了链表+Dijkstra算法)：
#include <stdio.h>
#include <string.h>
#define inf 10000000
constint Maxn = 200005;
 
intN,M;
intvisit[1001];//标记某个节点是否被求出最短距离
intfirst[1001];//存储每个节点为始点的链表的第一个边的标号
structEdge{
    inttarget;//终点
    intnext;//下一条边的标号
    intdt,ct;//边的长度和花费
}edge[Maxn];
 
structBNode{
    intdist,cost;
}Node[1001];//到达某点的最短路和花费
 
//相当于链表的头插发，很有意思。比用邻接矩阵高效多了
 
voidaddEdge(intindex, intu, intv, intd, intc){
    edge[index].next = first[u];//将这条边插入到u为初始节点的链表的头结点处
    edge[index].target = v;
    edge[index].dt = d;
    edge[index].ct = c;
    first[u] = index;
}
 
intfindMinNode(){//在剩下的所有节点中找最小的
    inti, Max = inf;
    intindex = 0;
    for(i = 1; i <= N; i++){
        if(Node[i].dist < Max && !visit[i]){
            Max = Node[i].dist;
            index = i;
        }
    }
    returnindex;
}
 
voiddijk(ints){
    inti;
    intflag = 1;
    Node[s].cost = Node[s].dist = 0;
    while(flag < N){//更新N-1次
        intx = findMinNode();
        if(!x)break;
        visit[x] = 1;
        flag++;
        for(i = first[x]; i != -1; i = edge[i].next){
            inttarget = edge[i].target;
            if(Node[x].dist + edge[i].dt < Node[target].dist && !visit[target]){//更新节点
                Node[target].dist = Node[x].dist + edge[i].dt;
                Node[target].cost = Node[x].cost + edge[i].ct;
            }elseif(Node[x].dist + edge[i].dt == Node[target].dist && !visit[target]){
            //如果存在多条路径，更新最小花费节点
                if(Node[x].cost + edge[i].ct < Node[target].cost){
                    Node[target].cost = Node[x].cost + edge[i].ct;
                }
            }
        }
    }
}
 
intmain(){
    intu, v, d, c;
    ints, t;
    while(scanf("%d %d",&N,&M) != EOF && (N != 0 || M != 0)){
        intindex = 0;
        memset(first,-1,sizeof(first));
        for(inti = 1; i <= N; i++){
            Node[i].dist = Node[i].cost = inf;
        }
 
        memset(visit, 0, sizeof(visit));
        for(inti = 0; i < M; i++){
            scanf("%d %d %d %d",&u,&v,&d,&c);
            addEdge(index, u, v, d, c);
            index++;
            addEdge(index, v, u, d, c);
            index++;
        }
        scanf("%d %d", &s, &t);
        dijk(s);
        printf("%d %d\n",Node[t].dist,Node[t].cost);
    }
}
/**************************************************************
    Problem: 1008
    User: 姜超
    Language: C++
    Result: Accepted
    Time:10 ms
    Memory:4160 kb
****************************************************************/

九度 题目1008：最短路径问题


联系
我们