CODEVS 1021 玛丽卡

//出队的点需要重置v，可能再入队松弛其他的点。 //还要注意如何记录路径，本题记录边比较方便，刘汝佳也讲了如何记录点，尤其注意追溯边的那个循环怎么写。 #include<bits/stdc++.h> using namespace std; const int maxn = 1010; const int inf = 0x3f3f3f3f; int tot, n, m, cnt; struct node{ int u, v, w, next; } edge[maxn*maxn]; int st[maxn], d[maxn], fe[maxn*maxn]; bool v[maxn]; void in(int a, int b, int c){ edge[++tot].u = a; edge[tot].v = b; edge[tot].w = c; edge[tot].next = st[a]; st[a] = tot; } void init(){ memset(v, 0, sizeof(v)); for(int i = 0; i <= n; i++) d[i] = inf; } void spfa(int begin, int end, int judge){ queue<int> q; init(); d[begin] = 0; v[begin] = 1; q.push(begin); while(!q.empty()){ int from = q.front(); q.pop(); v[from] = 0;//!!!!! for(int i = st[from]; i > 0; i = edge[i].next){ int to = edge[i].v; if(d[to] > d[from] + edge[i].w){ d[to] = d[from] + edge[i].w; if(judge) fe[to] = i;//不管是否要入队都需记录来边。 if(!v[to]){ v[to] = 1; q.push(to); } } } } } int main(){ cin >> n >> m; for(int j = 1, a, b, c; j <= m; j++){ cin >> a >> b >> c; in(a, b, c); in(b, a, c); } memset(fe, -1, sizeof(fe)); spfa(n, 1, 1); int ans = d[1]; //cout << ans << endl; for(int i = fe[1]; i > 0; i = fe[edge[i].u]){ //cout << edge[i].v << " "; int t = edge[i].w; //cout << t << endl; edge[i].w = inf; spfa(n, 1, 0); //cout << d[1] << endl; edge[i].w = t; ans = max(ans, d[1]); } cout << ans << endl; return 0; }