切换到宽版
  • 6362阅读
  • 0回复

RQNOJ341 [复制链接]

上一主题 下一主题
离线cpp_student
 
只看楼主 倒序阅读 0 发表于: 2009-07-31
SPFA

  1. /*
  2. 查看题目 Show Problem
  3. 题目:星门跳跃
  4. 问题编号:341 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
  5. My Flag:Accepted
  6. 题目类型
  7. 最短路  
  8. 描述
  9. 在EVE游戏中,宇宙被划分成为许多区域,每个区域中都有数目不定的星门,可以通过星门来跳跃到特定的区域(星门是双向的)。
  10. 现在你正参与BBE联军与MLGBD联盟的会战,但由于飞船受损,需要尽快回到后方的友军空间站进行维护。
  11. 试编写程序,计算出所须的最短的返回空间站时间。
  12. 为了简化问题,我们约定飞船所在的位置为区域1,空间站所在的位置为区域N。
  13. 问题规模:
  14. 对于80%的数据,1<N<=10000,1<M<50000;
  15. 对于100%的数据,1<N<=30000,1<M<150000,1<=X[],Y[]<=N,1<=Z[]<=4096;
  16. 输入格式
  17. 第1行,两个整数N,M,分别为区域的总数和星门的总数;
  18. 第2..M+1行,每行三个整数X[i],Y[i],Z[i],分别为星门连接的两个区域,以及跳跃所需时间;
  19. 输出格式
  20. 一个整数,返回空间站所需的最短时间。
  21. 样例输入
  22. 样例一
  23. 5 3
  24. 1 4 5
  25. 4 5 1
  26. 1 2 7
  27. 样例二
  28. 10 11
  29. 1 2 3
  30. 2 3 4
  31. 3 4 5
  32. 4 5 6
  33. 5 6 7
  34. 6 7 8
  35. 7 8 9
  36. 8 9 10
  37. 9 10 11
  38. 1 5 7
  39. 6 9 3  
  40. 样例输出
  41. 样例一
  42. 6
  43. 样例二
  44. 28  
  45. */
  46. #include<iostream>
  47. #include<climits>
  48. using namespace std;
  49. __int64 n,m,dis[100001];
  50. struct link
  51. {
  52.     int adjvex,len;
  53.     link *next;
  54. };
  55. struct point
  56. {
  57.     link *head;
  58. } ps[100001];
  59. bool mark[100001];
  60. int que[1000001],front,rear;
  61. void spfa(void){
  62.     dis[1]=0;
  63.     for (int i=2;i<=n;i++)
  64.         dis[i]=LLONG_MAX;
  65.     memset(mark,false,sizeof(mark));
  66.     front=rear=0;
  67.     que[rear++]=1;
  68.     mark[1]=true;
  69.     while (rear>front)
  70.     {
  71.         int i=que[front++];
  72.         mark[i]=false;
  73.         front%=1000001;
  74.         link *pp;
  75.         pp=ps[i].head;
  76.         while (pp!=NULL){
  77. //            if ((dis[pp->adjvex]!=LLONG_MAX)&&(dis[i]>dis[pp->adjvex]+pp->len)){
  78. //                dis[i]=dis[pp->adjvex]+pp->len;
  79. //                if (!mark[pp->adjvex])
  80. //                {
  81. //                    mark[pp->adjvex]=true;
  82. //                    que[rear++]=pp->adjvex;
  83. //                    rear%=30001;
  84. //                }
  85. //            }
  86.             if ((dis[i]!=LLONG_MAX)&&(dis[pp->adjvex]>dis[i]+pp->len)){
  87.                 dis[pp->adjvex]=dis[i]+pp->len;
  88.                 if (!mark[pp->adjvex])
  89.                 {
  90.                     mark[pp->adjvex]=true;
  91.                     que[rear++]=pp->adjvex;
  92.                     rear%=1000001;
  93.                 }
  94.             }
  95.             pp=pp->next;
  96.         }
  97.     }
  98. }
  99. int main (void){
  100.     int a,b,s;
  101.     scanf ("%d %d",&n,&m);
  102.     for (int i=0;i<m;i++){
  103.         scanf ("%d %d %d",&a,&b,&s);
  104.         link *p1,*p2;
  105.         p1=new link;
  106.         p2=new link;
  107.         p1->adjvex=a;
  108.         p1->len=s;
  109.         p1->next=ps[b].head;
  110.         ps[b].head=p1;
  111.         p2->adjvex=b;
  112.         p2->len=s;
  113.         p2->next=ps[a].head;
  114.         ps[a].head=p2;
  115.     }
  116.     spfa();
  117.     printf("%d",dis[n]);
  118. //    while (1);
  119.     return 0;
  120. }
快速回复
限100 字节
 
上一个 下一个