。。
这题一眼就看出就是一个二维DP
dp[i][j]表示到点i使用了j次免费边的最短距离
MD 卡SPFA。。
遂写dij。 AC
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
#define eps 1e-8
#define MAXN 11111
#define MAXM 111111
#define INF 111111111
using namespace std;
typedef pair<int, int> P;
vector<P>g[MAXN];
long long dis[MAXN][22];
int n, m, k;
struct node
{int v, num;long long w;node(){}node(int a, int b, long long c){v = a; num = b; w = c;}bool operator >(const node &cmp) const{return w > cmp.w;}
};
priority_queue<node, vector<node>, greater<node> > q;
void dij()
{for(int i = 1; i <= n; i++)for(int j = 0; j <= k; j++)dis[i][j] = INF;dis[1][0] = 0;q.push(node(1, 0, 0));while(!q.empty()){node tmp = q.top();q.pop();int u = tmp.v;int num = tmp.num;long long w = tmp.w;for(int i = 0; i < g[u].size(); i++){int v = g[u][i].first;long long tw = g[u][i].second;if(num < k && w < dis[v][num + 1]){dis[v][num + 1] = w;q.push(node(v, num + 1, w));}if(w + tw < dis[v][num]){dis[v][num] = w + tw;q.push(node(v, num, w + tw));}}}long long ans = dis[n][0];for(int i = 1; i <= k; i++)ans = min(ans, dis[n][i]);printf("%lld\n", ans);
}
int main()
{int u, v, w;while(scanf("%d%d%d", &n, &m, &k) != EOF){while(!q.empty()) q.pop();for(int i = 0; i <= n; i++) g[i].clear();for(int i = 0; i < m; i++){scanf("%d%d%d", &u, &v, &w);g[u].push_back(make_pair(v, w));g[v].push_back(make_pair(u, w));}dij();}return 0;
}