首页 > 代码库 > Tram---poj1847（简单最短路）
Tram---poj1847（简单最短路）
题目链接：http://poj.org/problem?id=1847
题意：给了N个交叉口，每个交叉口有自己能转到的交叉口。
注意这里：First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection.
即每一行的第二个数字代表该交叉口默认的通向，是不需要手动转的，剩下的交叉口想去的话都需要手动转一次。
现在想要从A口走到B口，走的路程想要转的次数时最少的，问最少转的值。
建图求最短路即可
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <queue>#include <stack>#include <algorithm>#include <map>#include <string>typedef long long LL;#define INF 0x3f3f3f3f#define met(a, b) memset(a, b, sizeof(a))#define N 515using namespace std;int G[N][N], n;void Floyd(){ for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) G[i][j] = min(G[i][j], G[i][k]+G[k][j]); }}int main(){ int a, b, num, k; while(scanf("%d %d %d", &n, &a, &b) != EOF) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) G[i][j] = INF; G[i][i] = 0; } for(int i=1; i<=n; i++) { scanf("%d", &k); for(int j=1; j<=k; j++) { scanf("%d", &num); if(j == 1) G[i][num] = 0; else G[i][num] = 1; } } Floyd(); if(G[a][b] == INF)puts("-1"); else printf("%d\n", G[a][b]); } return 0;}
Tram---poj1847（简单最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。