首页 > 代码库 > HDU3790最短路径问题

HDU3790最短路径问题

2024-07-17 05:17:37   219人阅读

最短路径问题

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


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 21 2 5 62 3 4 51 30 0
 

Sample Output
9 11
 

Source
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int MX=1<<30;int Road[1100][1100][2],n,fz[1100][2];int s,e;struct node{    int s,l,fee;};void dfs(int &l,int &fee){    node a,b;    a.s=s;    a.l=0;    a.fee=0;    l=fee=MX;    fz[a.s][0]=0;    fz[a.s][1]=1;    queue<node>q;    q.push(a);    while(!q.empty())    {        a=q.front();        q.pop();        for(int i=1;i<=n;i++)        {            b.s=i;            b.l=a.l+Road[a.s][i][0];            b.fee=a.fee+Road[a.s][i][1];            if(Road[a.s][i][0]!=MX&&               (fz[i][0]>b.l||(fz[i][0]==b.l&&fz[i][1]>b.fee)))            {                fz[i][0]=b.l;                fz[i][1]=b.fee;                if(b.s==e&&(l>b.l||(l==b.l&&fee>b.fee)))                {                    l=b.l;                    fee=b.fee;                }                q.push(b);            }        }    }}int main(){    int m;    while(scanf("%d%d",&n,&m)!=EOF)    {        int i,j,a,b,c,d;        if(n==0&&m==0)break;        for(i=0;i<=n;i++)        {            for(j=0;j<=n;j++)            {                 Road[i][j][0]=MX;                   Road[i][j][1]=MX;            }            fz[i][0]=MX;            fz[i][1]=MX;        }//初始化        for(i=0;i<m;i++)        {            scanf("%d%d%d%d",&a,&b,&c,&d);            if(c<Road[a][b][0]||(c==Road[a][b][0]&&Road[a][b][1]>d)){            Road[a][b][0]=c;            Road[b][a][0]=c;            Road[a][b][1]=d;            Road[b][a][1]=d;}        }        scanf("%d%d",&s,&e);        int l,fee;        dfs(l,fee);        printf("%d %d\n",l,fee);    }    return 0;}

 


联系
我们