【Aizu - 2249】Road Construction（最短路 Dijkstra算法）

Road Construction

Descriptions

Mercer国王是ACM王国的王者。他的王国里有一个首都和一些城市。令人惊讶的是，现在王国没有道路。最近，他计划在首都和城市之间修建道路，但事实证明他的计划的建设成本远高于预期。

为了降低成本，他决定通过从原计划中删除一些道路来制定新的施工计划。但是，他认为新计划应满足以下条件：

对于每对城市，都有一条连接它们的路线（一组道路）。
首都和每个城市之间的最小距离不会改变他原来的计划。

许多计划可能符合上述条件，但King Mercer希望以最低成本了解该计划。您的任务是编写一个程序，该程序读取其原始计划并以最低成本计算新计划的成本。

输入

输入包含多个数据集。每个数据集的格式如下。

N M
u₁ v₁ d₁ c₁
.
.
.
u_M v_M d_M c_M

每个数据集的第一行开始于两个整数，?和中号（1≤ ? ≤10000，0≤ 中号 ≤20000）。N和M分别表示原始计划中的城市数量和道路数量。

以下M行描述了原始计划中的道路信息。在我个行包含四个整数 u_i，v _i，d _i和c_i（1≤ u_i，v_i ≤ N，u_i ≠ v _i，1≤ d_i ≤1000，1≤ c_i ≤1000 ）。u_i，v _i，d _i和c_i表明有是连接道路u_i个城市和v _i个城市，其长度为d _i和它的成本需要建设c_i。

每条道路都是双向的。没有两条道路连接同一对城市。第一城市是王国的首都。

输入的结尾由包含两个由空格分隔的零的线表示。您不应将该行作为数据集处理。

输出

对于每个数据集，打印满足一行条件的计划的最低成本。

样本输入

样本输入的输出

题目链接

https://vjudge.net/problem/Aizu-2249

求出城市1到各个城市之间的最短距离，同时算出城市1到各个城市之间的最低花费

1000³Floyd显然会超时，而且这里没负数，Dijkstra算法再好不过了，下面我写的Dijkstra算法改了一下，用的二维数组d[i][j]，可以求出i到j的最短距离，虽然在这没什么用，但是用以后肯定用的到，这个可以直接拿来用，这个模板可以copy一下

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>1
#include 
#include 
#include 
#include <set>
#include 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 20000+5
#define P pair//first最短路径second顶点编号
using namespace std;
int N,M;
struct edge
{
    int to,dis,cost;
    edge(int to,int dis,int cost):to(to),dis(dis),cost(cost) {}
};
vectorG[Maxn];//G[i] 从i到G[i].to的距离为dis，花费的钱为cost
int d[Maxn][Maxn];//d[i][j]从i到j的最短距离
int sum[Maxn];//sum[i]，起点到i之间所需要的花费的钱
void Dijk(int s)
{
    priority_queue,greater >q;//按first从小到大出队
    for(int i=0; i<=N; i++)
        d[s][i]=INF;
    d[s][s]=0;
    q.push(P(0,s));
    while(!q.empty())
    {
        P p=q.top();
        q.pop();
        int v=p.second;//点v
        if(d[s][v]<p.first)
            continue;
        for(int i=0; i)
        {
            edge e=G[v][i];//枚举与v相邻的点
            if(d[s][e.to]>=d[s][v]+e.dis)
            {
                if(d[s][e.to]==d[s][v]+e.dis)//距离相等，比较谁花费的钱少
                    sum[e.to]=min(sum[e.to],e.cost);
                else//若d[s][e.to]>d[s][v]+e.dis，相求出最短距离，再求出最短距离所需要的钱
                    sum[e.to]=e.cost;
                d[s][e.to]=d[s][v]+e.dis;
                q.push(P(d[s][e.to],e.to));
            }
        }
    }
}
int main()
{
    IOS;
    while(cin>>N>>M,N+M)
    {
        MEM(sum,0);
        for(int i=1; i<=N; i++)
            G[i].clear();
        for(int i=0; i)
        {
            int u,v,d,c;
            cin>>u>>v>>d>>c;
            G[u].push_back(edge(v,d,c));
            G[v].push_back(edge(u,d,c));
        }
        Dijk(1);//城市1到各个城市的最短距离
        int ans=0;
        for(int i=2; i<=N; i++)
            ans+=sum[i];
        cout<endl;
    }
    return 0;
}

【AOJ】题解图论——最短路

【Aizu - 2249】Road Construction（最短路 Dijkstra算法）

Road Construction

相关

标签