寻找最短路径长度
- 格式：docx
- 大小：102.07 KB
- 文档页数：7
在EVE游戏中，宇宙被划分成为许多区域，每个区域中都有数目不定的星门，可以通过星门来跳跃到特定的区域（星门是双向的）。
现在你正参与BBE联军与MLGBD联盟的会战，但由于飞船受损，需要尽快回到后方的友军空间站进行维护。
试编写程序，计算出所须的最短的返回空间站时间。
为了简化问题，我们约定飞船所在的位置为区域1，空间站所在的位置为区域N。
问题规模：对于80%的数据，1<N<=10000，1<M<50000；对于100%的数据，1<N<=30000，1<M<150000，1<=X[],Y[]<=N，1<=Z[]<=4096；输入格式第1行，两个整数N,M，分别为区域的总数和星门的总数；第2..M+1行，每行三个整数X[i],Y[i],Z[i]，分别为星门连接的两个区域，以及跳跃所需时间；输出格式一个整数，返回空间站所需的最短时间。
样例输入样例输出实验代码：#include<iostream>#include<vector>#include<set>#include<queue>#include<string>#include<functional>#include<numeric>#include<algorithm>#include<math.h>using namespace std;#define Nmax 30001#define Mmax 150001#define Weightmax 5001class stop{private:int*section;int*Istravel;long int num_section;long int num_door;int **connection;public:stop(){num_door=0;num_section=0;};stop(int n,long int m){num_section=n;num_door=m;section=new int[num_section];Istravel=new int[num_section];connection=new int *[num_section];for(int i=0;i<num_section;i++)connection[i]=new int [num_section];for(int i=0;i<num_section;i++)for(int j=0;j<num_section;j++)connection[i][j]=0;for(int i=0;i<n;i++){section[i]=i+1;Istravel[i]=0;}}~stop(){num_section=0;num_door=0;for(int i=0;i<num_section;i++)delete[] connection[i];delete[] connection,section,Istravel;}void Set_door(long int m){ num_section=m; }void Set_connection(int n,long int m,multimap<int,vector<int>> mm) {vector<int> temp;vector<int>::iterator ita1,ita2,ita3;multimap<int,vector<int>>::iterator pos;pos=mm.begin();while( pos!=mm.end()){temp=pos->second;ita1=temp.begin();ita2=(++temp.begin());ita3=--temp.end();connection[*ita1-1][*ita2-1]=*ita3;temp.clear();++pos;}}void Print_connection(){cout<<"the connection is: "<<endl;for(int i=0;i<num_section;i++){for(int j=0;j<num_section;j++){cout<<connection[i][j]<<" ";}cout<<endl;}}int Get_section_num(){ return num_section;}long int Get_door_num(){return num_door;}int **Get_connection(){ return connection;}int * Get_section() {return section;}int *Get_Istravel() { return Istravel;}};long int Jump(int n,long int m,multimap<int,vector<int>> tt) {int i,k,weight[Nmax],start=1,end=n,flag=1;long int min=0;stop mm(n,m);mm.Set_connection(n,m,tt);int **map=mm.Get_connection();int *section=mm.Get_section();int *Istravel=mm.Get_Istravel();mm.Print_connection();Istravel[start-1]=1;weight[start-1]=Weightmax;for(i=0;i<n;i++){if(((i+1) != start)){if(map[start-1][i])weight[i]=map[start-1][i];elseweight[i]=Weightmax;}}while(flag){flag=0;min=Weightmax;for(i=0;i<n;i++){if(Istravel[i]==0){flag=1;break;}}for(i=0;i<n;i++){if(Istravel[i]==0 && weight[i]<min){min=weight[i];k=i;}}Istravel[k]=1;if(k+1==end)return min;for(i=0;i<n;i++){if(Istravel[i]==0){min=weight[i];if(map[k][i]>0 && (map[k][i]+weight[k])<min)weight[i]=map[k][i]+weight[k];}}}return -1;}主函数调用为：#include"stdafx.h"#include"example33.h"int main(){int n,start,end,tim;long int i,m;vector<int> temp;multimap<int,vector<int>> mm;cin>>n>>m;for(i=0;i<m;i++){cin>>start>>end>>tim;if(start<1 || start>n || end<1 || end>n){cout<<"it's wrong!"<<endl;break;}temp.clear();temp.push_back(start);temp.push_back(end);temp.push_back(tim);mm.insert(make_pair(start,temp));temp.clear();temp.push_back(end);temp.push_back(start);temp.push_back(tim);mm.insert(make_pair(end,temp));}cout<<Jump(n,m,mm)<<endl;return 0;}实验结果示例：实验结果示例2实验结果示例3：。
