首页 > 代码库 > POJ 3268 Silver Cow Party
POJ 3268 Silver Cow Party
题目链接：http://poj.org/problem?id=3268
思路：dijkstra先求出目标点X到各个点的最短路径，这个便是奶牛回来的最短路径，然后将矩阵转置，在求一次X到各个点的最短路径，这个路径便是奶牛去的最短路径，最后将这个个路径 相加比较即可得出答案。
代码：
#include <iostream>#include <cstring>#define INF 999999999using namespace std;int N,M,X;int e[1001][1001];//邻接矩阵储存地图 int m[1001][1001];//转置后的矩阵 int dis1[1001];//第一次求最短路径 int book[1001];int dis2[1001];//第二次求最短路径 int main(){ //freopen("data.txt","r",stdin); int a,b,c; int temp; int step; int res; while(cin>>N>>M>>X) { //第一步 res = 0; //初始化 memset(book,0,sizeof(book)); for(int i=1;i<=N;i++) dis1[i] = INF; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) { if(j==i) e[i][j] = 0; else e[i][j] = INF; } for(int i=1;i<=M;i++) { cin>>a>>b>>c; e[a][b] = c; } //初始化dis1数组 for(int i=1;i<=N;i++) { dis1[i] = e[X][i]; } //dijkstra算法核心 book[X] = 1; temp = X; for(int i=1;i<=N-1;i++) { step = INF; for(int j=1;j<=N;j++) { if(book[j]==0&&step>dis1[j]) { step = dis1[j]; temp = j; } } book[temp] = 1; for(int k=1;k<=N;k++) { if(dis1[k]>dis1[temp]+e[temp][k]) dis1[k] = dis1[temp]+e[temp][k]; } } //第二步 //矩阵反转 for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { m[i][j] = e[j][i]; } } //初始化dis2 for(int i=1;i<=N;i++) dis2[i] = INF; for(int i=1;i<=N;i++) { dis2[i] = m[X][i]; } memset(book,0,sizeof(book)); //dijkstra算法核心 book[X] = 1; temp = X; for(int i=1;i<=N-1;i++) { step = INF; for(int j=1;j<=N;j++) { if(book[j]==0&&step>dis2[j]) { step = dis2[j]; temp = j; } } book[temp] = 1; for(int k=1;k<=N;k++) { if(dis2[k]>dis2[temp]+m[temp][k]) dis2[k] = dis2[temp]+m[temp][k]; } } //第三步，进行相加比较得出结果 for(int i=1;i<=N;i++) { if(dis1[i]==INF||dis2[i]==INF) continue; else res = max(dis1[i]+dis2[i],res); } cout<<res<<endl; } return 0;}
POJ 3268 Silver Cow Party
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。