uva oj 567 - Risk(Floyd算法)

简介:
/*
一张有20个顶点的图上。
依次输入每个点与哪些点直接相连。
并且多次询问两点间,最短需要经过几条路才能从一点到达另一点。

bfs 水过
*/
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;

struct node{
   int x, step;
   node(){
   
   }
   node(int x, int step){
      this->x=x;
      this->step=step;
   }
}; 


vector<int>v[25]; 
queue<node>q;
int vis[25];


int b, e;

void bfs(){
   while(!q.empty())  q.pop();
   node cur;
   q.push(node(b, 0));
   while(!q.empty()){
       cur=q.front();
       q.pop();
       if(cur.x==e){
           printf("%2d to %2d: %d\n", b, e, cur.step);
           return;
       }
       int len=v[cur.x].size();
       for(int i=0; i<len; ++i){
             if(v[cur.x][i]==e){
             printf("%2d to %2d: %d\n", b, e, cur.step+1);
             return;
          }
          if(!vis[v[cur.x][i]]){
               vis[v[cur.x][i]]=1;
             q.push(node(v[cur.x][i], cur.step+1));
          } 
       }
   }
}

int main(){
    int n, u;
    int cnt=0;
    while(scanf("%d", &n)!=EOF){
        while(n--){
           scanf("%d", &u);
           v[1].push_back(u);
           v[u].push_back(1);
        }
        for(int i=2; i<=19; ++i){
           scanf("%d", &n);
           while(n--){
              scanf("%d", &u);
              v[i].push_back(u);
              v[u].push_back(i);
           }
        }
        scanf("%d", &n);
        printf("Test Set #%d\n", ++cnt);
        while(n--){
           scanf("%d%d", &b, &e) ;
           bfs();
           memset(vis, 0, sizeof(vis));
        }
        printf("\n");
        for(int i=1; i<=20; ++i)
           v[i].clear();
           
    } 
    return 0;
}
/*
   Floyd 才是正解!
*/
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;

int map[25][25];

void Folyd(){
   for(int k=1; k<=20; ++k)
      for(int i=1; i<=20; ++i)
         for(int j=1; j<=20; ++j)
            if(map[i][j] > map[i][k] + map[k][j])
               map[i][j] = map[i][k] + map[k][j];
}


int main(){
    int n, u, b, e;
    int cnt=0;
    while(scanf("%d", &n)!=EOF){
        memset(map, 0x3f, sizeof(map));
        while(n--){
           scanf("%d", &u);
           map[1][u]=map[u][1]=1;
        }
        for(int i=2; i<=19; ++i){
           scanf("%d", &n);
           while(n--){
              scanf("%d", &u);
              map[u][i]=map[i][u]=1;
           }
        }
        scanf("%d", &n);
        printf("Test Set #%d\n", ++cnt);
        Folyd();
        while(n--){
           scanf("%d%d", &b, &e) ;
           printf("%2d to %2d: %d\n", b, e, map[b][e]);
        }
        printf("\n");
    }
}









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3898362.html,如需转载请自行联系原作者
目录
相关文章
|
2月前
|
存储 算法
【数据结构与算法】二叉树基础OJ--下(巩固提高)
【数据结构与算法】二叉树基础OJ--下(巩固提高)
|
25天前
|
算法 分布式数据库
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
15 1
|
26天前
|
机器学习/深度学习 算法 C语言
【C/数据结构与算法】:10道链表经典OJ
【C/数据结构与算法】:10道链表经典OJ
13 1
|
26天前
|
算法
【C/数据结构与算法】:二叉树经典OJ
【C/数据结构与算法】:二叉树经典OJ
17 0
【C/数据结构与算法】:二叉树经典OJ
|
1月前
|
存储 算法 C语言
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
38 1
|
2月前
|
存储 算法 C语言
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)(上)
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)
43 2
|
2月前
|
存储 算法 IDE
数据结构与算法⑯(第四章_下)二叉树的层序遍历+判断完全二叉树+一道OJ
数据结构与算法⑯(第四章_下)二叉树的层序遍历+判断完全二叉树+一道OJ
34 1
|
2月前
|
算法
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)(下)
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)
13 1
|
2月前
|
算法 C++
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)(上)
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)
12 1
|
2月前
|
算法
Frogger(Floyd算法)
Frogger(Floyd算法)