返回顶部

收藏

杭电ACM 3790:最短路径问题C++解法

更多

Input

输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。

(1<n>&lt;=1000, 0<m>&lt;100000, s != t) <br />Output <br />输出 一行有两个数, 最短距离及其花费。 <br /> <br />Sample Input <br />3 2 <br />1 2 5 6 <br />2 3 4 5 <br />1 3 <br />0 0 <br />Sample Output <br />9 11 <br />

                                C++解法,代码转自:代码转自:http://blog.csdn.net/u011538668/

                                </m></n>
#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]);
    }
}

标签:ACM,3790,最短路径

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. Shaun 发表 2016-09-18 10:21:46 Lehmer快速求1e11以内质数个数
  2. 童燕群 发表 2014-07-12 11:34:38 Dijkstra算法求解最短路径分析
  3. tpircsboy 发表 2014-11-15 13:35:37 Codeforces Round 276
  4. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  5. tpircsboy 发表 2015-09-21 10:19:58 重建二叉树
  6. 落絮飞雁 发表 2016-10-27 00:20:53 ACM的意义
  7. 博主 发表 2009-08-26 04:00:00 暂别,acm
  8. tpircsboy 发表 2014-11-15 16:01:05 Codeforces Round 277
  9. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation
  10. 博主 发表 2015-01-21 12:27:02 UVA 题解
  11. Shaun 发表 2016-11-04 14:38:36 2016ICPC沈阳站承办总结(PC^2使用指南)
  12. 博主 发表 2010-03-31 04:00:00 感谢ACM以及HDUACMTEAM