链接：https://ac.nowcoder.com/acm/contest/884/J
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
Your are given an undirect connected graph.Every edge has a cost to pass.You should choose a path from S to T and you need to pay for all the edges in your path. However, you can choose at most k edges in the graph and change their costs to zero in the beginning. Please answer the minimal total cost you need to pay.
输入描述:
The first line contains five integers n,m,S,T,K.
For each of the following m lines, there are three integers a,b,l, meaning there is an edge that costs l between a and b.
n is the number of nodes and m is the number of edges. 输出描述:
An integer meaning the minimal total cost. 示例1
输入
3 2 1 3 1
1 2 1
2 3 2 输出
1
题目大意：给出点的个数n,边的个数m,起点s,终点t,然后你还可以使k条边的权值为0，问从s到e的最短路是多少。
题目思路：这个题题解的DP我没看懂就说一下用图论怎么做吧，我们可以分层建图，层与层之间 权值为0，表示用了一条边(单向边)，层内保留原值建图。具体如下图所示：
这样的话从第一层的起点1开始跑，跑到第二层的三需要1，第一层的3需要3，那么就表示使用一条边为0时，路程最短。具体这个题目就模拟一下建图过程就好了，然后用第一层的S作为起点，然后输出第k层E的最小值即可。这里注意分层建图之后，这就时最多 1000*1000个点，边数可能跟会到1e7所以head(链式前向星)数组还有边数组需要开到1e7否则会报错误，具体代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=1e7+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m,s,ee,t;
int head[maxn];
bool vis[maxn];
ll dis[maxn];
struct node{
ll e,next;
ll w;
}edge[maxn];
ll cnt=0;
void addedge1(ll u,ll v,ll w)
{
edge[cnt]=node{v,head[u],w};
head[u]=cnt++;
edge[cnt]=node{u,head[v],w};
head[v]=cnt++;
}
void addedge(ll u,ll v,ll w)
{
edge[cnt]=node{v,head[u],w};
head[u]=cnt++;
}
void spfa(ll st)
{
queue<int>q;for(int i=1;i<=(t+1)*n;i++) vis[i]=false,dis[i]=INF;
q.push(st);vis[st]=true;
dis[st]=0;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int e=edge[i].e;
if(dis[e]>dis[u]+edge[i].w)
{
dis[e]=dis[u]+edge[i].w;
if(!vis[e])
{
vis[e]=true;
q.push(e);
}
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%lld%lld%lld%lld%lld",&n,&m,&s,&ee,&t);
for(int i=1;i<=m;i++)
{
ll x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
addedge1(x,y,z);
for(int k=1;k<=t;k++)//层内赋权值
addedge1(k*n+x,k*n+y,z);
ll tempx=x,tempy=y;
for(int k=1;k<=t;k++)//层间负赋权值
{
addedge(tempx,k*n+y,0);
addedge(tempy,k*n+x,0);
tempx=k*n+x;
tempy=k*n+y;
}
}
spfa(s);
ll minl=dis[ee];
printf("%lld\n",dis[t*n+ee]);
return 0;
} 总结：记住分层最短路！！！！
京公网安备 11010502036488号