[BZOJ1579] [Usaco2009 Feb]Revamping Trails 道路升级（分层图最短路 + 堆优化dijk）

传送门

dis[i][j]表示第i个点，更新了j次的最短路

此题不良心，卡spfa

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #define N 50001 using namespace std; struct node bool operator > (const node& gg) const }; int n, m, k, cnt; int head[N], to[N << 1], next[N << 1], val[N << 1], dis[N][21]; bool vis[N][21]; priority_queue <node, vector <node>, greater <node> > q; inline int read() inline void add(int x, int y, int z) inline void dijkstra() if(x + 1 <= k && dis[v][x + 1] > dis[u][x]) } } } int main() dijkstra(); printf("%d\n", dis[n][k]); return 0; }

　　

上一篇：[BZOJ2287]【POJ Challenge】消失之物（DP）

下一篇：【模板】AC自动机

---

堆 dijkstra