|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXN 0x3f3f3f3f int cost[1005][1005]; int dis[1005]; bool vis[1005]; void dijkstra(int n){ memset(dis, MAXN, sizeof(dis)); memset(vis, false, sizeof(vis)); dis[2] = 0; while (true) { int cur = 0,mindis = MAXN; for (int i = 1; i <= n; i++) { if (vis[i]) { continue; } if (dis[i] < mindis) { mindis = dis[i]; cur = i; } } if (!cur) { break; } vis[cur] = true; for (int i = 1; i <= n; i++) { if (vis[i]) { continue; } if (cost[cur][i]!=MAXN && dis[cur]+cost[cur][i] < dis[i]) { dis[i] = cost[cur][i]+dis[cur]; } } } } int cnt[1005]; int dfs(int currNode,int n){ if (cnt[currNode] != -1) { return cnt[currNode]; } if (currNode == 2) { return 1; } int sum = 0; for (int i = 1; i <= n; i++) { if (cost[currNode][i] == MAXN) { continue; } if (dis[currNode] > dis[i]) { sum += dfs(i,n); } } return cnt[currNode] = sum; } int main(){ int n = 0, m = 0; while (scanf(" %d",&n) != EOF && n) { scanf(" %d",&m); memset(cost, MAXN, sizeof(cost)); for (int i = 1; i <= n; i++) { cost[i][i] = 0; } for (int i = 1; i <= m; i++) { int a = 0,b = 0,c = 0; scanf(" %d %d %d",&a,&b,&c); cost[a][b] = c; cost[b][a] = c; } dijkstra(n); memset(cnt, -1, sizeof(cnt)); cout << dfs(1,n) << endl; } return 0; } |
这个题数据好像有坑，如果用vector实现的邻接表会WAWAWA。。。嗯
然后题意那个sxbk的英语也是醉人，要是理解成最短路有多少条就哈哈了，应该是使到2节点的最短距离递减的节点序列有多少条。
然后你理解对了题意，又很脸好地用了邻接矩阵，嗯，估计还会T一阵子，原因是这个题还要卡DFS的优化问题，要使用记忆化搜索。
把这三点都注意了就能A了。（如果数据不坑，其实真是个好题）
