「 Luogu P2196 」 挖地雷

# 解题思路

跑 $\text{n}$ 遍 $\text{spfa}$ 并记录路径，找到比当前最长路长的就更新答案，并且将路径也更新，注意起点的处理。

 

# 附上代码

#include <iostream> #include <cstring> #include <cstdio> #include <queue> #define INF 123456789 using namespace std; int n, a[23], head[23], cnt, pre[23], Ans, ans[23], dis[23], TANS[23], t; bool vis[23]; queue<int> Q; struct edge { int nxt, u, v, w; }ed[23*23]; inline void addedge(int x, int y, int z) { ed[++cnt].nxt = head[x]; head[x] = cnt; ed[cnt].u = x, ed[cnt].v = y, ed[cnt].w = z; } inline int spfa(int s) { while (!Q.empty()) Q.pop(); memset(vis, 0, sizeof(vis)); for(int i=1; i<=n; i++) dis[i] = -INF; Q.push(s), dis[s] = a[s], vis[s] = 1, pre[s] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=head[u]; i; i=ed[i].nxt) { if(dis[ed[i].v] < dis[u] + ed[i].w) { dis[ed[i].v] = dis[u] + ed[i].w; pre[ed[i].v] = u; if(!vis[ed[i].v]) vis[ed[i].v] = 1, Q.push(ed[i].v); } } vis[u] = 0; } for(int i=1; i<=n; i++) { if(dis[i] > Ans) { Ans = dis[i]; for(int j=1; j<=n; j++) ans[j] = pre[j]; t = i; } } } int main() { scanf("%d", &n); int x; for(int i=1; i<=n; i++) scanf("%d", &a[i]); for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { scanf("%d", &x); if(x == 1) addedge(i, j, a[j]); } } for(int i=1; i<=n; i++) spfa(i); cnt = 0; for(int i=t; i; i=ans[i]) TANS[++cnt] = i; for(int i=cnt; i>=1; i--) printf("%d ", TANS[i]); printf("\n%d", Ans); }

 

转载于:https://www.cnblogs.com/bljfy/p/9634717.html