ACM-ICPC 2018 南京赛区网络预赛 L Magical Girl Haze - 分层最短路

 

 

思路：

分层最短路，在可以使k条边权值为0的情况下求点1到n的最短路

d[i][j]:=从1到i点用了j条免费边的最短路径

优先队列按距离从小到大排序，每次pop出来的都是已经更新好的点，用这个点更新其他点

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>

using namespace std;
#define ll long long
const int N=100005,M=300005;
const ll INF=0x7f7f7f7f;
struct proc{int to,cost,next;};
proc edge[M];
int head[N],vis[N][15];
int n,m,k,tot;
ll d[N][15];

struct node{
    int dot,bian;
    ll dis;
    node(int dot,int bian,ll dis):dot(dot),bian(bian),dis(dis){}
    bool operator<(const struct node&x)const{
        return x.dis<dis;
    }
};


void init(){
	memset(head,-1,sizeof(head));
	memset(d,INF,sizeof(d));
	memset(vis,0,sizeof(vis));
	tot=0;
}

void addEdge(int from,int to,int cost){
	edge[tot].to=to;
	edge[tot].cost=cost;
	edge[tot].next=head[from];
	head[from]=tot;
	tot++;
}

void Dijkstra(int s){
    d[s][0]=0;//从点1到s省了0条边的距离是0
    priority_queue<node>q;
    q.push(node(s,0,0));//按边的权值排序
    while(!q.empty()){
       node p=q.top();q.pop();
       int u=p.dot,lv=p.bian;
       if(vis[u][lv])continue;
       vis[u][lv]=1;
       ll len=p.dis;
       for(int i=head[u];i!=-1;i=edge[i].next){
           int v=edge[i].to;//当前点所到点的编号
           if(d[v][lv]>d[u][lv]+edge[i].cost){//不省这条边花费更小
               d[v][lv]=d[u][lv]+edge[i].cost;
               q.push(node(v,lv,d[v][lv]));
           }
           if(lv<k){//可省这条边
               if(d[v][lv+1]>d[u][lv]){//省了这条边花费更小
                   d[v][lv+1]=d[u][lv];
                   q.push(node(v,lv+1,d[v][lv+1]));
               }
           }
       }
    }
}

int main(){
	int T,s,e,c;
	scanf("%d",&T);
	while(T--){
		init();
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&s,&e,&c);
            addEdge(s,e,c);
		}
		if(k>=m){
            printf("0\n");
            continue;
		}
		Dijkstra(1);
		ll ans=d[n][0];
		for(int i=1;i<=k;i++){
            ans=min(ans,d[n][i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}