其实在博客园里写题解都挺应付的都是在洛谷写了之后
挑一部分粘过来
在洛谷写的也都是废话，是为了凑篇幅
主要就是代码
大体思路就一提
这题贪心不行废话
跑m遍SPFA更新最小值
注意数组记得清空
The Last:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 5005; int cnt, head[N << 1], n, m, x, minn = 0x3f3f3f3f, C[N], t, s, dis[N]; bool vis[N]; struct node{ int nxt, to, d, w; }e[N << 1]; int read() { int s = 0, w = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} return s * w; } void add(int x, int y, int w, int d) { e[++cnt].nxt = head[x]; e[cnt].to = y; e[cnt].w = w; e[cnt].d = d; head[x] = cnt; } void spfa (int ww) { queue<int> q; memset(dis, 50, sizeof(dis)); memset(vis, 0, sizeof(vis)); vis[1] = 1; q.push(1); dis[1] = 0; while (!q.empty()) { int he = q.front(); q.pop(); vis[he] = 0; for (int i = head[he]; i ;i = e[i].nxt) { if (dis[e[i].to] > dis[he] + e[i].d && e[i].w >= ww) { dis[e[i].to] = dis[he] + e[i].d; if (!vis[e[i].to]) { vis[e[i].to] = 1; q.push(e[i].to); } } } } } int main() { n = read(), m = read(), x = read(); for(int i = 1; i <= m; i++) { int x, y, d, l; x = read(), y = read(), d = read(), l = read(); add(x, y, l, d), add(y, x, l, d); C[i] = l; } // for(int i = 1; i <= n; i++) // printf("%d ", e[i].w); // printf("\n"); // sort(C + 1, C + 1 + m); for(int i = 1; i <= m; i++) { spfa(C[i]); minn = min(minn, (dis[n] + x / C[i])); } // for(int i = 1; i <= n; i++) // printf("%d ", dis[i]); // printf("\n"); printf("%d\n", minn); return 0; }
谢谢收看，祝身体健康！