迪杰斯克拉--双权值

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3790

题意：给你n个点，m条无向边，每条边都有长度d和花费c，给你起点s和终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有

多条路线，则输出花费最少的。

分析：本题是双重权值的最短路径问题，当然最法跟一般的最短路做法差不多。

#include <iostream>
#include <string.h>
#include <stdio.h>

const int N = 1005;
const int INF = 1<<29;

bool vis[N];
int d[N],c[N];
int map[N][N];
int cost[N][N];
int m,n,s,t;

void Init()
{
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            map[i][j] = (i == j) ? 0 : INF;
            cost[i][j] = (i == j) ? 0 : INF;
        }
    }
}

void Dijkstra(int cur)
{
    vis[cur] = 1;
    for(int i=1; i<=n; i++)
    {
        d[i] = map[cur][i];
        c[i] = cost[cur][i];
    }
    for(int i=2; i<=n; i++)
    {
        int k = cur;
        int minval = INF;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j] && d[j] < minval)
            {
                minval = d[j];
                k = j;
            }
        }
        vis[k] = 1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j])
            {
                if(d[j] > d[k] + map[k][j])
                {
                    d[j] = d[k] + map[k][j];
                    c[j] = c[k] + cost[k][j];
                }
                else if(d[j] == d[k] + map[k][j] && c[j] > c[k] + cost[k][j])
                    c[j] = c[k] + cost[k][j];
            }
        }
    }
    if(d[t] == INF) puts("1");
    else printf("%d %d
",d[t],c[t]);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0 && m==0)  break;
        Init();
        while(m--)
        {
            int u,v,x,y;
            scanf("%d%d%d%d",&u,&v,&x,&y);
            if((map[u][v] > x) || (map[u][v] == x && cost[u][v] > y))
            {
                map[u][v] = map[v][u] = x;
                cost[u][v] = cost[v][u] = y;
            }
        }
        scanf("%d%d",&s,&t);
        Dijkstra(s);
    }
    return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。