【图论杂题】：L.motor [分层图]

题目：

团队链接：motor

题面：

给定一张$n$个点$m$条边的带边权图
现在要从点$s$到点$t$
至多经过$k$条边时可不花费代价
求最小代价

范围：$n<=10000,m<=50000,k<=10$

样例：

输入：

5 10 1
1 5
1 2 4
1 4 3
2 4 2
2 5 100
5 3 24
4 5 12
2 1 1000
1 4 33
1 2 54
2 4 305

输出：

3

题解：

这个题，真没什么可说的，分层图板子题，，，之前写过的，但是之前自己画的那张图很不错，很好理解分层图，就再放一下吧。
但是，有一件很重要的事，要记录一下，djikstra+堆优化的时候，为什么不能把（S，0）写成（0，S），这是因为在pair中，两个变量是按第一关键字排序的！！！反过来的话就会按dis[]排序了，然后就WA，TLE等等（因为这个问题，调了一下午~~55555~）

代码

#include<bits/stdc++.h>
#define pii pair<int,int> 
#define fir first 
#define sec second 
using namespace std;
inline int read()
{
    int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int ocean=2e9+7;
const int sea=1e7+7;
const int pool=2e6+7;
struct see{
    int ver,edge,next;}e[sea];
priority_queue<pii,vector<pii>,greater<pii> >Q;
int n,m,k,S,T,ans,tot,dis[pool],v[pool],last[sea];
void add(int x,int y,int z){
    e[++tot].edge=z,e[tot].ver=y;e[tot].next=last[x];last[x]=tot;}
void dijkstra()
{
    memset(dis,127,sizeof(dis));dis[S]=0; Q.push(make_pair(0,S));	while(Q.size()){
    int x=Q.top().sec; Q.pop();if(v[x]) continue; v[x]=1;for(int i=last[x];i;i=e[i].next){
    int y=e[i].ver,z=e[i].edge;if(dis[y]>dis[x]+z){
    dis[y]=dis[x]+z;Q.push(make_pair(dis[y],y));}}}
}
int main()
{
    n=read(); m=read(); k=read(); S=read(); T=read();for(int i=1;i<=m;i++){
    int x,y,z;x=read(); y=read(); z=read();add(x,y,z); add(y,x,z);for(int j=1;j<=k;j++)add(j*n+x,j*n+y,z),add(j*n+y,j*n+x,z),add((j-1)*n+x,j*n+y,0),add((j-1)*n+y,j*n+x,0);}dijkstra(); ans=ocean;for(int i=0;i<=k;i++) ans=min(ans,dis[T+i*n]);printf("%d\n",ans);return 0;
}

Continue……