首页 > 代码库 > XDOJ_1159_最短路
XDOJ_1159_最短路
http://acm.xidian.edu.cn/problem.php?id=1159
首要要考虑重边和环,然后开放一个点就要更新相关最短路,而且更新的顺序有要求。WA了无数遍。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int n,m,t,a[305][305],ok[305]; int main() { while(~scanf("%d%d%d",&n,&m,&t)) { memset(a,0x3f,sizeof(a)); memset(ok,0,sizeof(ok)); for(int i = 0;i < n;i++) a[i][i] = 0; while(m--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(u == v) continue; a[u][v] = min(a[u][v],w); } while(t--) { int o; scanf("%d",&o); if(o == 0) { int x; scanf("%d",&x); if(ok[x]) printf("lab %d has been repaired!\n",x); else { ok[x] = 1; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { if(!ok[i] || !ok[j]) continue; a[j][x] = min(a[j][x],a[j][i]+a[i][x]); } } for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { if(!ok[i] || !ok[j]) continue; a[x][j] = min(a[x][j],a[x][i]+a[i][j]); } } for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { if(!ok[i] || !ok[j]) continue; a[i][j] = min(a[i][j],a[i][x]+a[x][j]); } } } } else { int u,v; scanf("%d%d",&u,&v); if(!ok[u] || !ok[v]) printf("help %d %d\n",u,v); else if(a[u][v] == INF) printf("no path\n"); else printf("%d\n",a[u][v]); } } } return 0; }
XDOJ_1159_最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。