http://acm.hdu.edu.cn/showPRoblem.php?pid=1142
给定一个无向图，要求从点1走到点2，对所走的路径有如下要求：当点a和点b连通时，只有从a到终点的最短路大于b到终点的最短路时，才可以从a走到b。问这样从起点走到终点这样的路径有多少条
题意有点费解，不是求最短路的条数！可以这么理解：把每个点到终点的最短路径作为权值，那么对于一条满足条件的路径，要求从起点到终点的权值是严格递减的。可以反向求最短路，求出终点到其他所有点的最短路，然后以起点开始进行记忆化搜索即可求出结果
#include <bits/stdc++.h>using namespace std;const int N = 1010;struct edge{ int to, cost, next;}g[N*N*2];int cnt, head[N];bool vis[N];int dis[N], num[N];int n, m;void add_edge(int v, int u, int cost){ g[cnt].to = u, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++;}void spfa(int s){ queue<int> que; memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis); que.push(s), dis[s] = 0, vis[s] = true; while(! que.empty()) { int v = que.front(); que.pop(); vis[v] = false; for(int i = head[v]; i != -1; i = g[i].next) { int u = g[i].to; if(dis[u] > dis[v] + g[i].cost) { dis[u] = dis[v] + g[i].cost; if(! vis[u]) que.push(u), vis[u] = true; } } }}int dfs(int v){ if(v == 2) return 1; if(num[v]) return num[v]; for(int i = head[v]; i != -1; i = g[i].next) { int u = g[i].to; if(dis[v] > dis[u]) num[v] += dfs(u); } return num[v];}int main(){ while(scanf("%d", &n), n) { scanf("%d", &m); cnt = 0; memset(head, -1, sizeof head); memset(num, 0, sizeof num); for(int i = 0; i < m; i++) { int v, u, c; scanf("%d%d%d", &v, &u, &c); add_edge(v, u, c), add_edge(u, v, c); } spfa(2); printf("%d/n", dfs(1)); } return 0;}新闻热点
疑难解答
