洛谷P2939 [USACO09FEB]改造路Revamping Trails(最短路)

题目描述

Farmer John dutifully checks on the cows every day. He traverses some of the M (1 <= M <= 50,000) trails conveniently numbered 1..M from pasture 1 all the way out to pasture N (a journey which is always possible for trail maps given in the test data). The N (1 <= N <= 10,000) pastures conveniently numbered 1..N on Farmer John's farm are currently connected by bidirectional dirt trails. Each trail i connects pastures P1_i and P2_i (1 <= P1_i <= N; 1 <= P2_i <= N) and requires T_i (1 <= T_i <= 1,000,000) units of time to traverse.

He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose K (1 <= K <= 20) trails to turn into highways, which will effectively reduce the trail's traversal time to 0. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1 to N.

TIME LIMIT: 2 seconds

约翰一共有N)个牧场.由M条布满尘埃的小径连接.小径可 以双向通行.每天早上约翰从牧场1出发到牧场N去给奶牛检查身体.

通过每条小径都需要消耗一定的时间.约翰打算升级其中K条小径,使之成为高 速公路.在高速公路上的通行几乎是瞬间完成的,所以高速公路的通行时间为0.

请帮助约翰决定对哪些小径进行升级,使他每天早上到牧场W花的时间最少.输出这个最少 的时间.

输入输出格式

输入格式:

* Line 1: Three space-separated integers: N, M, and K

* Lines 2..M+1: Line i+1 describes trail i with three space-separated integers: P1_i, P2_i, and T_i

输出格式:

* Line 1: The length of the shortest path after revamping no more than K edges

输入输出样例

输入样例#1: 

4 4 1 
1 2 10 
2 4 10 
1 3 1 
3 4 100 

输出样例#1: 

1 

说明

K is 1; revamp trail 3->4 to take time 0 instead of 100. The new shortest path is 1->3->4, total traversal time now 1.

如果你知道什么叫做分层图的话那就是个裸题

否则就是个神题

首先在原图上处理肯定是不好做

那么我们把图分层,具体来说建K+1张原图,图与图之间的边权为0,边为原图中的边

这样跑一个二维dijstra(真难写)就好了

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define Pair pair<int,int>
#define F first
#define S second
const int MAXN=1e6+10;
using namespace std;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,M,K;
int dis[MAXN][21],vis[MAXN][21];
struct node
{
    int u,v,w,nxt;
}edge[MAXN];
int head[MAXN],num=1;
inline void AddEdge(int x,int y,int z)
{
    edge[num].u=x;edge[num].v=y;edge[num].w=z;edge[num].nxt=head[x];
    head[x]=num++;
}
void Dijstra()
{
    memset(dis,0xf,sizeof(dis));
    dis[1][0]=0;//第i个点,第j层
    priority_queue< pair<int,Pair > > q;
    q.push(make_pair(0,make_pair(1,0)));//第一个表示点,第二个表示层 
    while(q.size()!=0)
    {
        while(vis[q.top().S.F][q.top().S.S]&&q.size()>0) q.pop();
        Pair p=q.top().second;
        vis[p.F][p.S]=1;
        for(int i=head[p.F];i!=-1;i=edge[i].nxt)
        {
            int will=edge[i].v;
            if(vis[will][p.S]==0&&dis[will][p.S]>dis[p.F][p.S]+edge[i].w) 
                dis[will][p.S]=dis[p.F][p.S]+edge[i].w,
                q.push(make_pair(-dis[will][p.S],make_pair(will,p.S)));
            if(p.S+1<=K&&vis[will][p.S+1]==0&&dis[will][p.S+1]>dis[p.F][p.S])
                dis[will][p.S+1]=dis[p.F][p.S],
                q.push(make_pair(-dis[will][p.S+1],make_pair(will,p.S+1)));
        }
    }
    printf("%d",dis[N][K]);
}
int main()
{
    memset(head,-1,sizeof(head));
    N=read();M=read();K=read();
    for(int i=1;i<=M;i++)
    {
        int x=read(),y=read(),z=read();
        AddEdge(x,y,z);
        AddEdge(y,x,z);
    }
    Dijstra();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

iOS开发-OpenGLES进阶教程

教程 OpenGLES入门教程1-Tutorial01-GLKit OpenGLES入门教程2-Tutorial02-shader入门 OpenGLES入门...

3369
来自专栏数据结构与算法

BZOJ1853: [Scoi2010]幸运数字(容斥原理)

首先在$10^{10}$内只含$6, 8$的数有$\sum_{i = 1}^{10} 2^i = 2046$个。

981
来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

3929
来自专栏机器之心

教程 | 如何使用TensorFlow中的高级API:Estimator、Experiment和Dataset

选自Medium 作者:Peter Roelants 机器之心编译 参与:李泽南、黄小天 近日,背景调查公司 Onfido 研究主管 Peter Roelant...

6807
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列十一:使用FFT变换实现图像卷积。

  本文重点主要不在于FFT的SSE优化,而在于使用FFT实现快速卷积的相关技巧和过程。   关于FFT变换,有很多参考的代码,特别是对于长...

5389
来自专栏转载gongluck的CSDN博客

H.264格式分析

一.H.264基本流结构 H.264 的基本流(elementary stream,ES)的结构分为两层,包括视频编码层(VCL)和网络适配层(NAL)。视频编...

6955
来自专栏技术专栏

Python3入门机器学习(三)- matplotlib基础与简单应用

2942
来自专栏移动开发面面观

OpenGL ES——导入.stl格式的3D模型

2094
来自专栏AIUAI

Caffe2 - (二十五) Detectron 之 utils 函数(3)

7254
来自专栏bboysoul

1067: 成绩评估

描述:我们知道,高中会考是按等级来的。90~100为A; 80~89为B; 70~79为C; 60~69为D; 0~59为E。 编写一个程序,对输入的...

842

扫码关注云+社区

领取腾讯云代金券