本文主要是介绍poj_3767——I Wanna Go Home,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
来源:http://poj.org/problem?id=3767
题目就不贴了,把代码和遇到的问题分享一下吧!
中间用G++交了很多次都是RE(运行错误),后来改用C++交发现还是有问题,一样的错误。这个程序中发现我写的一般都是用C++交比较牢靠,还有定义迪杰斯特拉 函数名的时候我用了个dijk(),然后我悲剧了,RE!你懂得,后来突发奇想改了一下交上去就AC了。郁闷死我啊!
呵呵,废话说完,下面说一下这个题,这个题目其实就是最短路的应用,在这里用的还是挺简单的,把迪杰斯特拉算法掌握就OK!
由于这个题中从1类城市走到2类城市后就不能再回去,只能穿过一次,所以先存为双向路,后面再根据不同类型的城市,把双向路变为单向路。
然后核心算法实现就OK!
代码:
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define inf 0xfffffff
#define size 610
int value[size][size];
int d[size];
int lead[size];
bool visit[size];
int n,m;
void djk()
{int x,y,z,tab,temp;memset(visit,0,sizeof(visit));for(x=1;x<=n;x++)d[x]=value[1][x];d[1]=0;visit[1]=1;for(x=1;x<n;x++){temp=inf;for(y=1;y<=n;y++){if(!visit[y]&&d[y]<temp){temp=d[y];tab=y;}}visit[tab]=true;for(z=1;z<=n;z++){if(!visit[z]&&d[z]>d[tab]+value[tab][z])d[z]=d[tab]+value[tab][z];}}if(d[2]==inf)cout<<"-1\n";elsecout<<d[2]<<endl;
}int main()
{while(cin>>n){if(n==0)break;int i,j,a,b,len;cin>>m;memset(lead,0,sizeof(lead));for(i=1;i<=n;i++)for(j=1;j<=n;j++)value[i][j]=inf;for(i=1;i<=m;i++){cin>>a>>b>>len;value[a][b]=value[b][a]=len;}for(i=1;i<=n;i++)cin>>lead[i];for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(lead[i]!=lead[j]){if(lead[i]==1&&lead[j]==2)value[j][i]=inf;else if(lead[i]==2&&lead[j]==1)value[i][j]=inf;}}}djk();}return 0;
}
在执行后面双向图转换单向图时有另外一种方法,
但是交上去也是RE。
for(i=1;i<=n;i++){if(lead[i]==2){for(j=1;j<=n;j++){if(lead[j]==1)value[i][j]=inf;}}}
很悲剧啊!
这篇关于poj_3767——I Wanna Go Home的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!