2018-ACM-ICPC-Nanjing-online-L

ACM-ICPC 2018 南京赛区网络预赛 L题

题目链接： https://nanti.jisuanke.com/t/31001

There are NN cities in the country, and MMdirectional roads from uu to v(1\le u, v\le n)v(1≤u,v≤n). Every road has a distance c_ici. Haze is a Magical Girl that lives in City 11, she can choose no more than KK roads and make their distances become 00. Now she wants to go to City NN, please help her calculate the minimum distance.

Input

The first line has one integer T(1 \le T\le 5)T(1≤T≤5), then following TT cases.

For each test case, the first line has three integers N, MN,M and KK.

Then the following MM lines each line has three integers, describe a road, U_i, V_i, C_iUi,Vi,Ci. There might be multiple edges between uu and vv.

It is guaranteed that N \le 100000, M \le 200000, K \le 10N≤100000,M≤200000,K≤10,
0 \le C_i \le 1e90≤Ci≤1e9. There is at least one path between City 11 and City NN.

Output

For each test case, print the minimum distance.

样例输入复制

样例输出复制

题目来源

ACM-ICPC 2018 南京赛区网络预赛

这个没啥好说的。

就是模板题。我的模板稍微修改一下就过了。

其实可以把一个点拆分成k个点，或者Dij转移的时候加一维记录状态。

#include <bits/stdc++.h>
using namespace std;
const long long INF=10000000000000000LL;
const int MAXN=100010;
int K;
struct qnode{
	int v;
        int tt;
	long long c;
	qnode(int _v=0, int _tt = 0,int _c=0):v(_v),tt(_tt),c(_c){}
	bool operator <(const qnode &r)const{
		return c>r.c;
	}
};
struct Edge{
	int v,cost;
	Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
bool vis[MAXN][11];
long long dist[MAXN][11];
void Dijkstra(int n,int start){
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++) {
          for (int k = 0; k <= K; k++)
            dist[i][k] = INF;
        }
	priority_queue<qnode>que;
	while(!que.empty())que.pop();
	dist[start][0]=0;
	que.push(qnode(start, 0, 0));
	qnode tmp;
	while(!que.empty()){
		tmp=que.top();
		que.pop();
		int u=tmp.v;
                int k = tmp.tt;
		if(vis[u][k])continue;
		vis[u][k]=true;
		for(int i=0;i<E[u].size();i++){
			int v=E[tmp.v][i].v;
			int cost=E[u][i].cost;
			if(!vis[v][k]&&dist[v][k]>dist[u][k]+cost){
				dist[v][k]=dist[u][k]+cost;
				que.push(qnode(v,k,dist[v][k]));
			}
                        if (k < K && !vis[v][k+1] && dist[v][k+1] > dist[u][k]) {
                          dist[v][k+1] = dist[u][k];
                          que.push(qnode(v, k+1, dist[v][k+1]));
                        }
		}
	}
}
void addedge(int u,int v,int w){
	E[u].push_back(Edge(v,w));

}

int main() {
  int T;
  int N,M;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++)E[i].clear();
    int u,v,w;
    while (M--) {
      scanf("%d%d%d", &u,&v, &w);
      addedge(u,v,w);
    }
    Dijkstra(N, 1);
    long long ans = INF;
    for (int i = 0; i <= K; i++)
      ans = min(ans, dist[N][i]);
    printf("%lld\n", ans);
  }
  return 0;
}