POJ_1847_思维最短路

POJ 1847

• 思路：每一个点都有多个出路,默认指出一条,问是否有最少转化次数到达终点,
• 条件转化为,原点的第一条边的权值为0,其余出边的权值为1,等价于转换开关的次数.
• 最短路模板

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
const int maxn = 105;
int e[maxn][maxn];
int n,m,start,end;
int dist[maxn];
bool vis[maxn];
int spfa() {
queue<int> que;
memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
que.push(start);
vis[start] = 1; dist[start] = 0;
while (!que.empty()) {
int cur = que.front(); que.pop();
vis[cur] = 0;
for (int i=1; i<=n; i++) {
if (dist[i] > dist[cur] + e[cur][i]) {
dist[i] = dist[cur] + e[cur][i];
if (!vis[i]) {
vis[i] = 1;
que.push(i);
}
}
}
}
return dist[end];
}
int main() {
//	freopen("a.txt","r",stdin);
cin >> n >> start >> end;
int k,backup,cur;
memset(e,0x3f,sizeof e);
for (int i=1; i<=n; i++) {
cin >> k; backup = k;
while (k--) {
cin >> cur;
if (k == backup-1) {
e[i][cur] = 0;
}
else e[i][cur] = 1;
}
}
int ans = spfa();
if (ans == 0x3f3f3f3f) printf("-1",ans);
else printf("%d",ans);
return 0;
}

最后

以上就是狂野黄蜂为你收集整理的POJ_1847_思维最短路的全部内容，希望文章能够帮你解决POJ_1847_思维最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。