最短路径问题（最短路径）

Love The Way You Lie 2022-08-01 14:48 256阅读 0赞

# 最短路径问题 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 16506    Accepted Submission(s): 4940**

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

[浙大计算机研究生复试上机考试-2010年][-2010]

**这是一题最短路径题目但是他的路径上权值不只是长度还有花费！这一点需要注意**

**一下！主要思路就是当它们的长度相等时就选择花费最少的那个！**

**还要注意的一点就是：C++的cin会超时，用scanf就能ok！我还**

**对比了一下啊啊，太吓人了，差距太大了！**

**下次一定要注意了！**

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    const int maxnum=1010;
    const int infinity=0x3f3f3f3;
    struct node
    {
        int d;
        int p;
    };
    node map[maxnum][maxnum];
    int vis[maxnum];
    int dis[maxnum];
    int pri[maxnum];
    int n,m;
    void djsta(int st)
    {
        int i,j,min_d,min_p,p;
        for(i=1;i<=n;i++)
        {
            dis[i]=map[st][i].d;
            pri[i]=map[st][i].p;
        }//算距离
        memset(vis,0,sizeof(vis));
        vis[st]=1;
        for(i=1;i<=n;i++)//循环次数！
        {
            min_d=infinity;
            min_p=infinity;
            for(j=1;j<=n;j++)
            {
                if(!vis[j]&&(dis[j]<min_d||vis[j]==min_d&&pri[j]<min_p))
                {
                    p=j;
                    min_d=dis[j];
                    min_p=pri[j];
                }
            }//找到最小之后，开始更新！
            vis[p]=1;//记录
            for(j=1;j<=n;j++)
            {
                if(!vis[j]&&(map[p][j].d+dis[p]<dis[j]||map[p][j].d+dis[p]==dis[j]&&map[p][j].p+pri[p]<pri[j]))
                {
                    dis[j]=map[p][j].d+dis[p];
                    pri[j]=map[p][j].p+pri[p];
                }
            }
        }
    }
    int main()
    {
        int a,b,c,d,e,f,i,j;
        while(cin>>n>>m,(m+n))
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    map[i][j].d=infinity;
                    map[i][j].p=infinity;
                }
            }
            while(m--)
            {
               scanf("%d%d%d%d",&a,&b,&c,&d);
              //  cin>>a>>b>>c>>d;
                if(map[a][b].d>c||map[a][b].d==c&&map[a][b].p>d)
                {
                    map[a][b].d=map[b][a].d=c;
                    map[a][b].p=map[b][a].p=d;
                }
            }
            scanf("%d%d",&e,&f);
         //   cin>>e>>f;
            djsta(e);
            cout<<dis[f]<<" "<<pri[f]<<endl;
        }
    }

[-2010]: http://acm.hdu.edu.cn/search.php?field=problem&key=%D5%E3%B4%F3%BC%C6%CB%E3%BB%FA%D1%D0%BE%BF%C9%FA%B8%B4%CA%D4%C9%CF%BB%FA%BF%BC%CA%D4-2010%C4%EA&source=1&searchmode=source