[Sample 1]
4 6
1 2
1 2 10
1 3 5
1 4 1
2 3 4
2 4 1
3 4 10

[Sample 2]
5 7
1 1 1
1 2 70
1 3 70
1 4 70
1 5 70
2 5 70
3 5 70
4 5 70

[Sample 1]
No
2

[Sample 2]
Yes
213

这题就是Spfa.

Program defence;
const
   maxn=90000;
   maxm=500000;
   inf=2139062143;
type
   dis_arr=record
              s:longint;
              d:array[1..maxn] of longint;
           end;
var
   n,m,i,j:longint;
   w:array[1..maxn] of longint;
   head,edge,next,weight:array[1..maxm] of longint;
   size:longint;
   d1,d2:dis_arr;
   queue:array[1..6000000] of longint;

Procedure addedge(u,v,w:longint);
begin
   inc(size);
   edge[size]:=v;
   weight[size]:=w;
   next[size]:=head[u];
   head[u]:=size;
end;
Procedure addedge_main;
var
   u,v,w:longint;
begin
   read(u,v,w);
   addedge(u,v,w);addedge(v,u,w);
end;
Procedure spfa(var d:dis_arr);
var
   i,j,now,p:longint;
begin
   i:=1;j:=1;queue[1]:=d.s;
   fillchar(d.d,sizeof(d.d),127);d.d[d.s]:=0;
   while (i<=j) do
   begin
      now:=queue[i];
      p:=head[now];
      while (p<>0) do
      begin
         if (d.d[now]+weight[p]<d.d[edge[p]]) then
         begin
            inc(j);
            queue[j]:=edge[p];
            d.d[edge[p]]:=d.d[now]+weight[p];
         end;
         p:=next[p];
      end;
      inc(i);
   end;
end;
Procedure print;
var
   i,j:longint;
   ans:int64;
   flag:boolean;
begin
   flag:=false;    ans:=0;
   for i:=2 to n-1 do
   begin
      if d1.d[i]<>inf then ans:=ans+int64(w[i]+d1.d[i]);
      if (d1.d[i]>d2.d[i]) then
      begin
         if not(flag) then begin flag:=true; writeln('No'); end
         else write(' ');
         write(i);
      end;
   end;
   if not(flag) then
   begin
      writeln('Yes');
      writeln(ans);
   end
   else writeln;
end;
begin
//   assign(input,'defence.in');
//   reset(input);
   fillchar(head,sizeof(head),0);
   fillchar(edge,sizeof(edge),0);
   fillchar(next,sizeof(next),0);
   size:=0;
   read(n,m); d1.s:=1;d2.s:=n;
   for i:=2 to n-1 do read(w[i]);
   for i:=1 to m do
   begin
      addedge_main;
   end;
   spfa(d1);spfa(d2);
   print;
end.

朴素的传递闭包

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100+10)
#define MAXM (4500+10)
bool f[MAXN][MAXN]={0};
int n,m;
int main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		f[x][y]=1;
	}
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				f[i][j]=f[i][j]||f[i][k]&&f[k][j];
	int tot=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			if (i!=j&&!(f[i][j]||f[j][i])) {tot--;break;}

		tot++;
	}
//	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) cout<<f[i][j]<<' ';

	cout<<tot;
	return 0;
} 

Floyd 遍历

注意由于可能在第n步后，所以必须枚3方的

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (2000+10)
#define MAXX (1000+10)
int n,x[MAXN],y[MAXN];
double dis(int i,int j)
{
	return sqrt(pow(abs(double(x[i]-x[j])),2)+pow(abs(double(y[i]-y[j])),2));
}
double d[MAXN][MAXN];
int main()
{
	int ii=1;
	while (1)
	{
		scanf("%d",&n);
		if (n==0) break;
		for (int i=1;i<=n;i++)
		{
			scanf("%d%d",&x[i],&y[i]);
		}



	//	for (int i=1;i<=n;i++) cout<<d[i]<<' ';
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<i;j++)
				d[i][j]=d[j][i]=dis(i,j);
		}
		for (int k=1;k<=n;k++)
			for (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++)
					d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));





		printf("Scenario #%dn",ii);
		printf("Frog Distance = %.3lfnn",d[1][2]);
//		cout<<d[1];



		ii++;
	}
	return 0;
}

裸Floyd

Program P1125;
const
   maxn=100;
   maxedge=10;
   NULL=-2139062144;
var
   n,i,j,k,m,v,t,ans:longint;
   f:array[1..maxn,1..maxn] of longint;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
begin
   read(n);
   while (n<>0) do
   begin
      fillchar(f,sizeof(f),128);
      for i:=1 to n do
      begin
         f[i,i]:=0;
         read(m);
         for j:=1 to m do
         begin
            read(v,t);
            f[i,v]:=t;
         end;
      end;

      for k:=1 to n do
         for i:=1 to n do
            for j:=1 to n do
               if (f[i,k]<>NULL) and (f[k,j]<>NULL) then
                  if (f[i,k]+f[k,j]<f[i,j]) or (f[i,j]=NULL) then f[i,j]:=f[i,k]+f[k,j];
      ans:=maxlongint;

      v:=0;
      for i:=1 to n do
      begin
         t:=f[i,1];
         for j:=1 to n do
         begin
            if f[i,j]=NULL then break else t:=max(f[i,j],t);
         end;
         if f[i,j]=NULL then continue;
         if t<ans then begin v:=i; ans:=t; end;

      end;
      if (ans=maxlongint) then writeln('disjoint') else writeln(v,' ',ans);



      read(n);
   end;
end.

这题只能对每一个点查一遍……

有向图的话能用floyd，可是迫于时限用了SPFA。

Program aa;
const
   maxk=10000;
   maxn=10000;
   maxm=10000;
var
   k,n,m,i,j,l:longint;
   a:array[1..maxk] of longint;
   q:array[1..maxn] of longint;
   edge,next,head:array[1..maxm] of longint;
   size:longint;
   res,num,b:array[1..maxn] of boolean;

procedure add(u,v:longint);
begin
   inc(size);
   edge[size]:=v;
   next[size]:=head[u];
   head[u]:=size;
end;


procedure spfa;
var
   i,j,p,now,v:longint;
begin
   i:=1;j:=1;
   while (i<=j) do
   begin
      now:=q[i];
      p:=head[now];
      while p<>0 do
      begin
         v:=edge[p];
         if not(b[v]) then
         begin
            b[v]:=true;
            inc(j);
            q[j]:=v;
         end;



         p:=next[p];
      end;
      inc(i);
   end;
   for i:=1 to n do
      res[i]:=res[i] and b[i];

end;

begin
   size:=0;
   fillchar(head,sizeof(head),0);
   fillchar(edge,sizeof(edge),0);
   fillchar(next,sizeof(next),0);
   fillchar(b,sizeof(b),false);
   fillchar(res,sizeof(res),true);
   fillchar(num,sizeof(num),false);
   read(k,n,m);
   for i:=1 to k do read(a[i]);
   for i:=1 to m do
   begin
      read(j,l);
      add(j,l);
   end;

   for i:=1 to k do
      if not(num[a[i]]) then
      begin
         num[a[i]]:=true;
         q[1]:=a[i];
         fillchar(b,sizeof(b),false);
         b[q[1]]:=true;
         spfa;
      end;
   l:=0;
   for i:=1 to n do if res[i] then inc(l);
   writeln(l);



end.

注意普通路径是双向的

program P3259;
var
   f,n,m,w,i,j:longint;
   s,e,t:longint;
   map:array[1..2500,1..3] of longint;
   wmap:array[1..300,1..3] of longint;
   d:array[1..2500] of longint;
   flag:boolean;
procedure relax(u,v,w:longint);
begin
   if (d[v]>d[u]+w) then
   begin
      d[v]:=d[u]+w;
      flag:=false;
   end;
end;
procedure bellman_ford;
var
   i,j:longint;
begin
   for i:=1 to n do
   begin
      flag:=true;
      for j:=1 to m do
      begin
         relax(map[j,1],map[j,2],map[j,3]);
         relax(map[j,2],map[j,1],map[j,3]);

      end;
      for j:=1 to w do relax(wmap[j,1],wmap[j,2],-wmap[j,3]);
      if flag then break;
   end;

   if flag then writeln('NO') else writeln('YES');
end;
begin
   read(f);
   while f>0 do
   begin
      fillchar(map,sizeof(map),0);
      fillchar(wmap,sizeof(wmap),0);
      fillchar(d,sizeof(d),0);

      read(n,m,w);
      for i:=1 to m do
      begin
         read(map[i,1],map[i,2],map[i,3]);
      end;
      for i:=1 to w do read(wmap[i,1],wmap[i,2],wmap[i,3]);
      bellman_ford;
      dec(f);
   end;
end.