问题 B: 小说

时间限制: 1 Sec  内存限制: 128 MB
提交: 88  解决: 36
[提交] [状态] [命题人:admin]

 

题目描述

由于小X是一位奆老，奆老总是忙得一刻也停不下来。他刚刚准备完食物，小X童年的挚友小S和小Z来找他帮忙了……
小S和小Z十分喜欢看网络写手“25”的小说，但由于需要付费才能阅读，而小S和小Z的零花钱有非常少，他们只能找小X靠黑科技侵入给网站，把小说给他们。
然而小X又非常的爱慕虚荣，他要小S和小Z到自己家里来取小说。
小S、小Z和小X都居住在扬中市，扬中市共有n个小区，m条主干道（假设每条主干道都是双行线）。小S家住在1号小区，小X家住在n号小区。小S每经过一条主干道需要耗费z点体力，但由于小S的人脉非常广，每当他到达一个小区，他都会和好友攀谈直到体力回满。
由于小Z也希望能看到小说，所以他答应帮助小S k次，这k次小S经过主干道不需要耗费体力。
由于小S生性懒惰，他希望耗费最少的体力到达小X家，请问他最少耗费多少体力？
注意：如果小S到小X家可以一路上都由小Z背着，那么体力上限为0；
如果小S到不了小X家，小S会很伤心，体力上限为-1；

 

输入

第1行三个整数n,m,k，意思如题目描述。
第2到第n+1行是x,y,z指走连接x号小区和y号小区的主干道要耗费z点体力

 

输出

一行一个整数，表示小S最少耗费的体力。

 

样例输入

复制样例数据

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

样例输出

4

 

提示

小S的行走路线：1->3->2->5，其中2->5这条主干道由小Z帮助小S通过。

对于30%的数据：n<=20;m<=100;
对于60%的数据：n<=100;m<=1000;
对于100%的数据：n<=1000;m<=10000;z<=1000000;

题解：有k次机会 ，与以前做过的一个题很像，每次使用一次机会就去到新的一层，建好图之后跑一遍 最短路最大值。

AC:

#include <bits/stdc++.h>
#include <hash_map>
#include <string>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m,p;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node{
    int e,next;
    ll w;
}edge[maxn];
ll cnt=0;
int head[maxn];
ll dis[maxn];
bool vis[maxn];
void addedge(int u,int v,ll w)
{
    edge[cnt]=node{v,head[u],w};
    head[u]=cnt++;
}
void spfa()
{
    queue<int>q;
    q.push(1);
    for(int i=1;i<=n*(p+2);i++) dis[i]=INF;
    dis[1]=0;vis[1]=true;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=false;
        for(int i=head[u];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            ll temp=max(dis[u],edge[i].w);
            if(dis[e]>temp)
            {
                dis[e]=temp;
                if(!vis[e])
                {
                    q.push(e);
                    vis[e]=true;
                }
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%lld%lld%lld",&n,&m,&p);
    for(int i=1;i<=m;i++)
    {
        int x,y;ll w;
        scanf("%d%d%lld",&x,&y,&w);
        for(int k=0;k<=p;k++)
        {
            addedge(k*n+x,k*n+y,w);
            addedge(k*n+y,k*n+x,w);
        }
        for(int k=1;k<=p;k++)
        {
            addedge((k-1)*n+x,k*n+y,0);
            addedge((k-1)*n+y,k*n+x,0);
        }
    }
    spfa();
    if(dis[p*n+n]==INF) printf("-1\n");
    else printf("%lld\n",dis[p*n+n]);
    return 0;
}

这个题意确实有点难懂