HDU3790-最短路径问题（dijkstra算法）

时间：2022-02-14 09:41:09

最短路径问题

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

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 0Sample Output9 11
   题目解析：注意两点1、去掉重复的路径，选择较短的。读入重时时如果路径长度相同，则选择花费较小的。2、不能用记录路径然后回溯的方法求最小花费，因为如果某两点之间有多条路径相等，则路径只能记录一种，不能根据此得出花费，应该先按照路径松弛，如果路径相等的话按照花费松弛！ 代码如下
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1010
int map[N][N],f[N][N],path[N],d[N],visited[N],fee[N];
dijkstra(int v0,int vt,int n)
{
    int v,i,min,w,next,sum=0,k;
    memset(visited,0,sizeof(visited));
    for(v=0;v<n;v++)
    {
        d[v]=0x7FFFFFFF;//初始化为权值
fee[v]=0x7FFFFFFF;
        visited[v]=0;//初始化过程 
    }
    path[v0]=v0;
    d[v0]=fee[v0]=0;
    visited[v0]=1;
    for(i=1,v=v0;i<n;i++)
    {        
        for(w=0;w<n;w++)
        {
            if(visited[w]==0&&map[v][w]!=0x7FFFFFFF)
{
if(d[v]<d[w]-map[v][w])
{
d[w]=d[v]+map[v][w];
fee[w]=fee[v]+f[v][w];
path[w]=v;
}
else if(d[v]==d[w]-map[v][w])
{
if(fee[v]<fee[w]-f[v][w])
fee[w]=fee[v]+f[v][w];
}
}
        }
        min=0x7FFFFFFF;
        for(w=0;w<n;w++)
            if(visited[w]==0&&d[w]<min)
            {
                v=w;
                min=d[w];
            }
        visited[v]=1;//加入标记
    }

   /*for(i=0;i<n;i++)//记录具体路径用的，本题可以不要
    {
        if(i==v0) continue;
        printf("从%d到%d最短路为 :%d\t",v0,i,d[i]);
        next=path[i];
printf("%d--",i);
        while(next!=path[next])
        {
            printf("%d--",next);
            next=path[next];
        }
        printf("%d\n",v0);
    }*/


/*for(i=0;i<n;i++)//利用回溯路径的方法求最小花费，在路径有相等的时候不可取
{
if(i!=vt) continue;
next=vt;
while(next!=path[next])
{
k=path[next];
sum+=f[k][next];
next=path[next];
}
break;
}
printf("%d %d\n",d[vt],sum);
*/
printf("%d %d\n",d[vt],fee[vt]);
}


int main()
{
    int n,m,i,j,a,b,x,y,s,t;
    while(scanf("%d %d",&n,&m),n&&m)
    {
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                map[i][j]=0x7FFFFFFF;
        for(i=0;i<m;i++)
        {
            scanf("%d %d %d %d",&a,&b,&x,&y);
            if(x<map[a-1][b-1])
            {
                map[a-1][b-1]=map[b-1][a-1]=x;
                f[a-1][b-1]=f[b-1][a-1]=y;
}
else if(x==map[a-1][b-1])//路径相同则取花费小的
{
if(y<f[a-1][b-1])
f[a-1][b-1]=f[b-1][a-1]=y;
}

        }
        scanf("%d %d",&s,&t);
        dijkstra(s-1,t-1,n);
    }
    system("pause");
    return 0;
}
/*
3 2
1 2 5 6
2 3 4 5
1 3

//下面的数据会测试两条路径一样长的时候的花费，会有错误，记录路径的时候不能保证花费是最少的。
5 7
1 2 2 1
2 4 6 15
4 5 4 6
5 3 2 7
3 1 9 3
3 2 3 7
3 4 3 4
1 4
*/
标签：

相关文章