新浪微博 登陆  注册   设为首页 加入收藏

学PHP >> PHP >> 杭电ACM HDU 3790 最短路径问题

杭电ACM HDU 3790 最短路径问题

查看次数3714 发表时间2013-06-09 02:41:38

最短路径问题Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7754    Accepted Submission(s): 2314Prob...

最短路径问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7754    Accepted Submission(s): 2314


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


 

Recommend
notonlysuccess

 

c、c++、gcc提交需要把注释去掉,不然会WA,因为这个我WA了N次

#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
",dis[b-1],pp[b-1]);
    }
}


 


(转发请注明转自:学PHP)    


  相关推荐




  发表评论
昵称:
(不超过20个字符或10个汉字)
内容: