jzoj 2051. 【8.18】极其简单的最短路问题

发布于 2019-03-31  5 次阅读


题目描述

小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
]]>