【Beijing WC2012】 冻结

Beijing WC2012】 冻结"/>

【Beijing WC2012】 冻结

【题目链接】

            点击打开链接

【算法】

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

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

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 55
#define MAXM 2010const 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 <typename T> inline void read(T &x)
{int f = 1; x = 0;char c = getchar();for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';x *= f;
}
template <typename T> inline void write(T x)
{if (x < 0){putchar('-');x = -x;}if (x > 9) write(x/10);putchar(x%10+'0');
}
template <typename T> 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<int,int> > q;pair<int,int> cur;for (i = 1; i <= n; i++){for (j = 0; j <= k; j++){dist[i][j] = INF;}}dist[1][0] = 0;q.push(make_pair(1,0));inq[1][0] = 1;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] = 1;q.push(make_pair(e[i].to,cur.second)); } }if ((cur.second + 1 <= k) && (dist[cur.first][cur.second] + e[i].cost / 2 < dist[e[i].to][cur.second+1])){dist[e[i].to][cur.second+1] = dist[cur.first][cur.second] + e[i].cost / 2;if (!inq[e[i].to][cur.second+1]){inq[e[i].to][cur.second+1] = 1;q.push(make_pair(e[i].to,cur.second+1));}}}}		
}int main() {read(n); read(m); read(k);for (i = 1; i <= m; i++){read(a); read(b); read(t);add(a,b,t);add(b,a,t);}spfa(1);for (i = 0; i <= k; i++) ans = min(ans,dist[n][i]);writeln(ans);return 0;}