首页 > 代码库 > POJ 1603 Risk
POJ 1603 Risk
最短路问题。
题意是说:前面19行是 相邻关系,无向图,后面是询问最短。
Floyd最简单。不过我用的SPFA。其实就是求最短路,不过没有距离了,只是每次 +1 。
注意最后一行需要输出一个空行。贡献PE一发。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; vector<int>g[21]; int dis[21][21]; bool sp[21]; int n,m; void SPFA(int start) { queue<int>q; bool vis[21]; memset(vis,0,sizeof(vis)); q.push(start); dis[start][start]=0; vis[start]=1; while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=0;j<g[u].size();j++) { int v=g[u][j]; if(dis[start][v]>dis[start][u]+1) { dis[start][v]=dis[start][u]+1; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { int nn=1; while(scanf("%d",&m)!=EOF) { for(int i=1;i<21;i++) g[i].clear(),sp[i]=0; int v; while(m--) { scanf("%d",&v); g[1].push_back(v); g[v].push_back(1); } for(int i=2;i<20;i++) { scanf("%d",&m); while(m--) { scanf("%d",&v); g[i].push_back(v); g[v].push_back(i); } } for(int i=1;i<21;i++) for(int j=1;j<21;j++) dis[i][j]=INF; scanf("%d",&m); int start,thend; printf("Test Set #%d\n",nn++); while(m--) { scanf("%d%d",&start,&thend); if(!sp[start]) { SPFA(start); sp[start]=1; } printf("%d to %d: %d\n",start,thend,dis[start][thend]); } printf("\n"); } }
POJ 1603 Risk
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。