题目描述

小C终于被小X感动了，于是决定与他看电影，然而小X距离电影院非常远，现在假设每条道路需要花费小X的时间为1，由于有数以万计的好朋友沿路祝贺，导致小X在通过某些路不得不耗费1的时间来和他们聊天，尽管他希望尽早见到小C，所以他希望找到一条最快时间到达电影院的路。
一开始小X在1号点，共有N个点，M条路，电影院为T号点。

输入

第一行3个正整数，分别为n，m，t
以下m行，每行3个数，表示连接的编号以及权值
（注意，可能会有重边）

输出

一行一个数，表示1到t的最短路

思路

spfa+优化
重点就在优化这了
用邻接表存储边，可以在spfa时减少判断次数
然后就可以飞起了

type
  arr=record
        x,y,w,next:longint;
      end;
var
  edge:array[0..10000000] of arr;
  ls,t,state:array[0..10000000] of int64;
  exits:array[0..1000000] of boolean;
  i,j,k,n,m,q,p,o,s,l:longint;
procedure spfa;
var
  head,tail,i,j:longint;
begin
  state[1]:=0;
  head:=0; tail:=1;
  exits[1]:=true;
  t[1]:=1;
  repeat
    inc(head);
    i:=ls[t[head]];
    while i<>0 do
      begin
        with edge[i] do
          begin
            if state[x]+w<state[y] then
              begin
                state[y]:=state[x]+w;
                if exits[y]=false then
                  begin
                    inc(tail);
                    t[tail]:=y;
                    exits[y]:=true;
                  end;
              end;
            i:=next;
          end;
      end;
      exits[t[head]]:=false;
    until head=tail;
end;
begin
  assign(input,'short.in');
  reset(input);
  assign(output,'short.out');
  rewrite(output);
  fillchar(state,sizeof(state),63);
  readln(n,m,l);
  j:=1;
  for i:=1 to m do
    begin
      readln(q,p,o);
      edge[j].x:=q;
      edge[j].y:=p;
      edge[j].w:=o;
      edge[j].next:=ls[edge[j].x];
      ls[edge[j].x]:=j;
      inc(j);
      edge[j].x:=p;
      edge[j].y:=q;
      edge[j].w:=o;
      edge[j].next:=ls[edge[j].x];
      ls[edge[j].x]:=j;
      inc(j);

    end;

  spfa;

    writeln(state[l])
end.