传送门
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; }
上一篇：[BZOJ1578] [Usaco2009 Feb]Stock Market 股票市场（DP）
下一篇：[BZOJ3545] [ONTAK2010]Peaks（线段树合并 + 离散化）
堆 dijkstra
