【题目链接】

点击打开链接

【算法】

dist[i][j]表示到达i号城市，使用了j次魔法，所用时间的最小值

那么，dist[i][j]可以转移到dist[k][j+1]和dist[k][j],一边spfa一边dp，即可

【代码】

#include
using namespace std;
#define MAXN 55
#define MAXM 2010

const int INF = 1e9;

int i,n,m,k,a,b,t,ans = INF,tot;
int head[MAXN],inq[MAXN][MAXN],dist[MAXN][MAXN];

struct Edge
{
int to,cost,nxt;
} e[MAXM];

template inline void read(T &x)
{
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - ''; x *= f; } template inline void write(T x)
{
if (x < ) { putchar('-'); x = -x; } if (x > ) write(x/);
putchar(x%+'');
}
template inline void writeln(T x)
{
write(x);
puts("");
}
inline void add(int u,int v,int w)
{
tot++;
e[tot] = (Edge){v,w,head[u]};
head[u] = tot;
}
inline void spfa(int s)
{
int i,j;
queue< pair > q;
pair cur;
for (i = ; i <= n; i++)
{
for (j = ; j <= k; j++)
{
dist[i][j] = INF;
}
}
dist[][] = ;
q.push(make_pair(,));
inq[][] = ;
while (!q.empty())
{
cur = q.front();
inq[cur.first][cur.second] = false;
q.pop();
for (i = head[cur.first]; i; i = e[i].nxt)
{
if (dist[cur.first][cur.second] + e[i].cost < dist[e[i].to][cur.second])
{
dist[e[i].to][cur.second] = dist[cur.first][cur.second] + e[i].cost;
if (!inq[e[i].to][cur.second])
{
inq[e[i].to][cur.second] = ;
q.push(make_pair(e[i].to,cur.second));
}
}
if ((cur.second + <= k) && (dist[cur.first][cur.second] + e[i].cost / < dist[e[i].to][cur.second+]))
{
dist[e[i].to][cur.second+] = dist[cur.first][cur.second] + e[i].cost / ;
if (!inq[e[i].to][cur.second+])
{
inq[e[i].to][cur.second+] = ;
q.push(make_pair(e[i].to,cur.second+));
}
}
}
}
}

int main() {

    read(n); read(m); read(k);  
    for (i = ; i <= m; i++)  
    {  
            read(a); read(b); read(t);  
            add(a,b,t);  
            add(b,a,t);  
    }  
    spfa();

    for (i = ; i <= k; i++) ans = min(ans,dist\[n\]\[i\]);

    writeln(ans);

    return ;

}