-
UID:2181
-
- 注册时间2006-10-28
- 最后登录2009-10-31
- 在线时间2小时
-
- 发帖10
- 搜Ta的帖子
- 精华0
- OI财富160
- 威望62
- 贡献值0
- 交易币0
-
访问TA的空间加好友用道具
|
SPFA - /*
- 查看题目 Show Problem
- 题目:星门跳跃
- 问题编号:341 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
- My Flag:Accepted
- 题目类型
- 最短路
-
- 描述
- 在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],分别为星门连接的两个区域,以及跳跃所需时间;
- 输出格式
- 一个整数,返回空间站所需的最短时间。
- 样例输入
- 样例一
- 5 3
- 1 4 5
- 4 5 1
- 1 2 7
- 样例二
- 10 11
- 1 2 3
- 2 3 4
- 3 4 5
- 4 5 6
- 5 6 7
- 6 7 8
- 7 8 9
- 8 9 10
- 9 10 11
- 1 5 7
- 6 9 3
- 样例输出
- 样例一
- 6
- 样例二
- 28
-
- */
- #include<iostream>
- #include<climits>
- using namespace std;
- __int64 n,m,dis[100001];
- struct link
- {
- int adjvex,len;
- link *next;
- };
- struct point
- {
- link *head;
- } ps[100001];
- bool mark[100001];
- int que[1000001],front,rear;
- void spfa(void){
- dis[1]=0;
- for (int i=2;i<=n;i++)
- dis[i]=LLONG_MAX;
- memset(mark,false,sizeof(mark));
- front=rear=0;
- que[rear++]=1;
- mark[1]=true;
- while (rear>front)
- {
- int i=que[front++];
- mark[i]=false;
- front%=1000001;
- link *pp;
- pp=ps[i].head;
- while (pp!=NULL){
- // if ((dis[pp->adjvex]!=LLONG_MAX)&&(dis[i]>dis[pp->adjvex]+pp->len)){
- // dis[i]=dis[pp->adjvex]+pp->len;
- // if (!mark[pp->adjvex])
- // {
- // mark[pp->adjvex]=true;
- // que[rear++]=pp->adjvex;
- // rear%=30001;
- // }
- // }
- if ((dis[i]!=LLONG_MAX)&&(dis[pp->adjvex]>dis[i]+pp->len)){
- dis[pp->adjvex]=dis[i]+pp->len;
- if (!mark[pp->adjvex])
- {
- mark[pp->adjvex]=true;
- que[rear++]=pp->adjvex;
- rear%=1000001;
- }
- }
- pp=pp->next;
- }
- }
- }
- int main (void){
- int a,b,s;
- scanf ("%d %d",&n,&m);
- for (int i=0;i<m;i++){
- scanf ("%d %d %d",&a,&b,&s);
- link *p1,*p2;
- p1=new link;
- p2=new link;
- p1->adjvex=a;
- p1->len=s;
- p1->next=ps[b].head;
- ps[b].head=p1;
- p2->adjvex=b;
- p2->len=s;
- p2->next=ps[a].head;
- ps[a].head=p2;
- }
- spfa();
- printf("%d",dis[n]);
- // while (1);
- return 0;
- }
|