题目:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1858
uva访问不到的可以去vjudge上:https://vjudge.net/problem/UVA-10917
题目大意是说有两个点1,2. 从1出发走到2,每次只走可以make progress的路径, 所谓的make progress的A到B的边指的是从存在B到2的某条路比A到2的任何路的长度都要小,实际上就是B到2的最短路比A到2的最短路要短。可以用单源最短路求出2出发的所有最短路,然后从1开始做一个DFS就可以求出正确答案。但是需要注意的就是这个DFS要记忆化一下,否则会TLE
AC代码:
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int MAXN = 1005; const int MAXM = 1000005; const int INF = (int) 1e9; int cntedge; struct EDGE { int from, to, weight, next_edge = -1; EDGE() {} EDGE(int f, int t, int w, int n) : from(f), to(t), weight(w), next_edge(n) {} } edge[MAXM << 1]; int head[MAXN]; bool vis[MAXN]; long long dist[MAXN]; inline void init(int n, int m) { fill(vis, vis + n, false); fill(dist, dist + n, INF); fill(head, head + n, -1); for (int i = 0; i < m; ++i) { edge[i].next_edge = -1; } cntedge = 0; } inline void addedge(int from, int to, int weight) { edge[cntedge] = EDGE(from, to, weight, head[from]); head[from] = cntedge++; } struct nd { long long d; int v; nd(long long _d, int _v) : d(_d), v(_v) {} friend bool operator>(const nd &a, const nd &b) { return a.d > b.d; } }; void dijkstra(int s) { dist[s] = 0; priority_queue<nd, vector<nd>, greater<nd>> q; q.push(nd(0, s)); while (!q.empty()) { nd p = q.top(); q.pop(); if (vis[p.v])continue; long long u = p.v; vis[u] = true; for (int e = head[u]; e != -1; e = edge[e].next_edge) { int v = edge[e].to; int w = edge[e].weight; if (p.d + w < dist[v] && !vis[v]) { dist[v] = p.d + w; q.push(nd(dist[v], v)); } } } } int dp[MAXN]; int validPathCnt(int st, int ed) { if (st == ed) { return 1; } if (dp[st] != -1)return dp[st]; int ret = 0; for (int e = head[st]; e != -1; e = edge[e].next_edge) { if (dist[edge[e].to] <= dist[st])continue; ret += validPathCnt(edge[e].to, ed); } return dp[st] = ret; } int main() { while (true) { static int n, m; scanf("%d", &n); if (!n)break; scanf("%d", &m); init(n + 2, m * 2 + 2); for (int i = 0; i < m; ++i) { static int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } dijkstra(2); fill(dp, dp + n + 1, -1); printf("%d\n", validPathCnt(2, 1)); } return 0; }
Comments | NOTHING