题意:求1到n的最大载重量
分析:那么就是最大路上的最小的边权值,改变优先规则.
#include#include #include #include using namespace std;typedef long long ll;const int N = 1e3 + 10;const int E = 1e5 + 10;const int INF = 0x3f3f3f3f;struct Edge { int v, w, nex; Edge() {} Edge(int v, int w, int nex) : v (v), w (w), nex (nex) {} bool operator < (const Edge &r) const { return w < r.w; }}edge[E];int head[N];int d[N];bool vis[N];int n, m, e;void init(void) { memset (head, -1, sizeof (head)); e = 0;}void add_edge(int u, int v, int w) { edge[e] = Edge (v, w, head[u]); head[u] = e++;}void Dijkstra(int s) { memset (d, 0, sizeof (d)); memset (vis, false, sizeof (vis)); d[s] = INF; priority_queue que; que.push (Edge (s, 0, 0)); while (!que.empty ()) { int u = que.top ().v; que.pop (); if (vis[u]) continue; vis[u] = true; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v, w = edge[i].w; if (!vis[v] && d[v] < min (d[u], w)) { d[v] = min (d[u], w); que.push (Edge (v, d[v], 0)); } } }}int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { init (); scanf ("%d%d", &n, &m); int mx = 0; for (int u, v, w, i=1; i<=m; ++i) { scanf ("%d%d%d", &u, &v, &w); if (n == 1 && u == 1 && v == 1) mx = max (mx, w); add_edge (u, v, w); add_edge (v, u, w); } printf ("Scenario #%d:\n", ++cas); if (n == 1) { printf ("%d\n", mx); continue; } Dijkstra (1); printf ("%d\n\n", d[n]); } return 0;}