导航竞争{silver题2} 

【问题描述】

农民约翰的汽车安装的两个导航仪在选择路线时经常出现冲突。

他居住区域的地图上有N（2 <= N <= 10,000）个结点和M(1 <= M <= 50,000)条有向边，边i连接节点A_i (1 <= A_i <= N) 和 B_i (1 <= B_i <= N)。两个结点之间可能有多条有向边。约翰的家住在结点1，他的农场在结点N。

两个导航仪使用同一份地图，但是对一同一条边，他们标注为不同驾驶时间。对于边i， i第一个导航仪标注P_i的时间，第二个导航仪标注Q_i的时间，皆为[1..100,000]的整数。

约翰开车从家里出发去他的牧场，每当他经过一条边的时候，比如从结点X到结点Y，若某个导航仪认为这不是从结点X到农场的最短路径上的一部分的时候，就会产生抱怨。若两个导航仪都不认为，则都会产生抱怨。

请帮助约翰找到一条合适的路径，使得在他的行程中，两个导航仪抱怨的次数最少。若在经过某条边时，两个导航仪均抱怨，则抱怨次数加2。

【文件输入】gpsduel.in

第一行两个整数N和M。

接下来M行，每行四个整数，分别表示A_i， B_i ，P_i， Q_i。

【文件输出】gpsduel.out

    一行，一个整数，表示最少的抱怨次数。

【输入样例1】

5 7

3 4 7 1

1 3 2 20

1 4 17 18

4 5 25 3

1 2 10 1

3 5 4 14

2 4 6 5

【输出样例1】

1

【样例1说明】

如果约翰选择的路径是1 - >2 - >4 - >5，则第一导航抱怨1 - >2路（它宁愿用1 - >3路代替）。对于其余的2 - >4 - >5，这两个导航都不会抱怨。

把bao数组的初始值赋为2，表示每条边被抱怨的次数。

首先把所有的边反过来，分别用p，q数组作为权值求N点到各点的最短路。

在求最短路的过程中，记下到某一结点的最短路径中直接与该结点相连的那条路（仅有一条）。

然后dec这些边的bao值。

最后从N点开始再求一次最短路。

dist[1]就是要求的答案。

（1500ms+的时间还是太弱了，最短路的算法需要优化。

SPFA应该会强一点。）

（不过既然会写SPFA就懒得重新打一遍最短路了）

var list,dist,start,finish,u,v,q,p,bao:array[0..100000] of longint;
      temp,tip,num,n,m,i:longint;
      used:array[0..50000] of boolean;
     st:array[0..50000] of string;
     use:array[0..100000] of string;

procedure qsort(a,b:longint);
var i,j,x,temp:longint;
begin
i:=a;
j:=b;
x:=u[(i+j) div 2];
repeat
 while u[i]<x do inc(i);
 while u[j]>x do dec(j);
 if i<=j then begin
  temp:=u[i];
  u[i]:=u[j];
  u[j]:=temp;
  temp:=v[i];
  v[i]:=v[j];
  v[j]:=temp;
  temp:=p[i];
  p[i]:=p[j];
  p[j]:=temp;
  temp:=q[i];
  q[i]:=q[j];
  q[j]:=temp;
  inc(i);
  dec(j);
  end;
until i>j;
if i<b then qsort(i,b);
if j>a then qsort(a,j);
end;

procedure deal;
var i,now:longint;
begin
start[u[1]]:=1;
now:=u[1];
for i:=2 to m do
 if u[i]<>now then
  begin
   finish[now]:=i-1;
   now:=u[i];
   start[now]:=i;
  end;
 finish[now]:=m;
end;

procedure dijkstra;
var i,j,min,pos,num,mm:longint;
       tip:string;
begin
for i:=1 to n do dist[i]:=maxlongint;
dist[n]:=0;
fillchar(used,sizeof(used),false);
for i:=1 to n-1 do
 begin
  min:=maxlongint;
  for j:=1 to n do
   if not used[j] then
    if dist[j]<min then
     begin
      min:=dist[j];
      pos:=j;
     end;
  used[pos]:=true;
  for j:=start[pos] to finish[pos] do
   if dist[pos]+p[j]<dist[v[j]] then
    begin
     dist[v[j]]:=dist[pos]+p[j];
     list[v[j]]:=j;
    end;
 end;
for i:=1 to n-1 do dec(bao[list[i]]);
end;

procedure dijkstra1;
var i,j,pos,min:longint;
begin
for i:=1 to n do dist[i]:=maxlongint;
dist[n]:=0;
fillchar(used,sizeof(used),false);
for i:=1 to n-1 do
 begin
  min:=maxlongint;
  for j:=1 to n do
   if not used[j] then
    if dist[j]<min then
     begin
      min:=dist[j];
      pos:=j;
     end;
    used[pos]:=true;
  for j:=start[pos] to finish[pos] do
   if dist[pos]+bao[j]<dist[v[j]] then
    dist[v[j]]:=dist[pos]+bao[j];
 end;
end;

begin
//assign(input,‘silver2.in‘);
//assign(output,‘silver2.out‘);
//reset(input);
//rewrite(output);
readln(n,m);
for i:=1 to m do
  readln(u[i],v[i],p[i],q[i]);
for i:=1 to m do
 begin
  temp:=u[i];
  u[i]:=v[i];
  v[i]:=temp;
 end;
qsort(1,m);
deal;
for i:=1 to m do bao[i]:=2;

dijkstra;
for i:=1 to m do p[i]:=q[i];
dijkstra;
dijkstra1;
writeln(dist[1]);

//close(input);
//close(output);
end.

（其实刚开始我把最短路径的每一条边都记下来了，

感谢YHZ的提醒……毕竟我们刚开始理解错的方式如出一辙。）

USACO2014OPEN导航竞争（silverT2）