Pascal(fpc 3.0.2) 解法, 执行用时: 6ms, 内存消耗: 256K, 提交时间: 2019-01-07 18:12:04

program NOI98_5;
 const
   MaxN = 99;     {服务器数的上限}
   MaxK = 9999;    {数据包数的上限}
 type
   TPackage = record   {数据包类型}
     Send: Word;    {发出时刻}
     Source: Byte;   {源服务器}
     Target: Byte;   {目的服务器}
   end;
   TLink = record    {传输线的时间类型}
     Short: Byte;    {最短传输时间}
     Long: Byte;    {最长传输时间}
   end; 
 var   N: Byte;    {服务器数}
   K: Word;     {数据包数}
   T: Word;     {输出时刻}
   P: Word;     {输出时刻后还在网络中传输的数据包数}
   Index: array [1 .. MaxN] of Byte; 
           {Index[I]——地址为I的服务器序号}
   Links: array [1 .. MaxN, 1.. MaxN] of TLink;  
         {Links[I, J]——服务器I的服务器J的传输时间}
   Packages: array [1 .. 10000] of TPackage; 

 procedure Init;     {输入数据}
   var
     I, J: Word;
     M: Word;      {传输线路数}
     S1, S2: Byte;    {当前传输线相连的两个服务器序号}
     Time: Word;      {当前传输线路的传输时间}
     PackageID: Longint;   {数据包编号}
   Begin   
     Reset(Input);    
     Readln(N);     {读服务器数}
     for I := 1 to N do begin  {度入每个服务器地址，计算Index表}
       Read(J);
       Index[J] := I;
     end;
     Readln(M);     {读传输线路输}
     FillChar(Links, Sizeof(Links), 0);  {Links表初始化}
     for I := 1 to M do begin      {输入每条线路的信息}
       Readln(S1, S2, Time);  {读相连的两台服务器地址和传输时间}
       S1 := Index[S1];   {计算这两台服务器的序号}
       S2 := Index[S2];
       if (Links[S1,S2].Short=0)or(Links[S1,S2].Short>Time) then   {计算该线路的最短传输时间和最长传输时间}
         Links[S1, S2].Short := Time;
       if Links[S1, S2].Long < Time then 
         Links[S1, S2].Long := Time;
       Links[S2, S1] := Links[S1, S2];
     end;
     Readln(K);     {读数据包数}
     for I := 1 to K do   {读每一个数据包的信息}
       with Packages[I] do
         Readln(PackageID, Send, Source, Target);
         {读第I个数据包的编号，起始发送时间，源服务器地址，目的服务器地址}
     Readln(T);     {读入输出时刻}
     Close(Input);
   end;

function Alive(It: TPackage): Boolean;
{模拟数据包It在T时刻还在网络中传输，则返回True；否则返回False}
  var
    I, J: Byte;
    Time: Word;
    Receive: array [1 .. MaxN] of Word; 
{Receive[I]：服务器I收到下一个数据的时刻}
    Accepted: array [1..MaxN] of Boolean;      
{Accepted[I]：为服务器I接收It的标志}
  begin
     Alive := True;
     FillChar(Receive, Sizeof(Receive), $FF);  
       {初始时，所有服务器未收到任何数据包}
     FillChar(Accepted, Sizeof(Accepted), False);
     Receive[Index[It.Source]] := It.Send;
       {源服务器在发送了It后开始接受下一个数据包}
     if It.Source <> It.Target then 
         Accepted[Index[It.Target]] := True;
       {若源服务器与目的服务器不同，则确定目的服务器收到数据包It}
     repeat
         I := 1;    {计算最早收到下一个数据包的服务器I}
         for J := 2 to N do   
           if Receive[J] < Receive[I] then I := J;
         if Receive[I] = $FFFF then 
           Break;    {若所有服务器收到It，则返回false}
         if not Accepted[I] then begin
         {若服务器未接收数据包It，则搜索与服务器I相连的服务器}
           for J := 1 to N do
             if Links[I, J].Short <> 0 then begin
                Time := Receive[I] + Links[I, J].Short;
            if Time < Receive[J] then Receive[J] := Time;
                {若服务器J能在Receive[J]前收到来自服务器I发来的数据包}
if Receive[I] + Links[I, J].Long > T then Exit;
                {若在该线路上传输It将超是，则返回True}
             end;
           Accepted[I] := True;  {设定服务器I收到It标志}
         end;
         Receive[I] := $FFFF;  {设服务器I转发过It标志}
     until False;
     Alive := False;    {It在TimeLine时刻前结束传输}
  end;

procedure Main;    {统计T时刻后还在网络中传输的数据包数}
   var
     Y: Word;
   begin
     P := 0;
     for Y := 1 to K do
       if Alive(Packages[Y]) then Inc(P);
   end;

 procedure Out;    {输出}
   begin
     Rewrite(Output);
     Writeln(P);
     Close(Output);
   end;

 begin
   Init;   
   Main;    
   Out;     
 end.
 

C++(clang++ 11.0.1) 解法, 执行用时: 20ms, 内存消耗: 460K, 提交时间: 2023-03-18 16:53:33

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXK=10001,INF=0x7FFFFFF;
using namespace std;
struct packet
{
	int id,s,t,stime;
}P[MAXK];
int N,M,K,S,T,dia,QuestTime,Ans;
int mapping[MAXN],adjm[MAXN][MAXN],dist[MAXN][MAXN],farest[MAXN];
void init()
{
	int i,j,a,b,v;
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&a);
		mapping[a]=i;
		for (j=1;j<=N;j++)
			adjm[i][j]=INF;
		adjm[i][i]=0;
	}
	scanf("%d",&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&v);
		a=mapping[a];b=mapping[b];
		if (v>farest[a]) farest[a]=v;
		if (v>farest[b]) farest[b]=v;
		adjm[a][b]=adjm[b][a]=v;
	}
	scanf("%d",&K);
	for (i=1;i<=K;i++)
		scanf("%d%d%d%d",&P[i].id,&P[i].stime,&P[i].s,&P[i].t);
	scanf("%d",&QuestTime);
}
void floyd()
{
	int i,j,k;
	for (i=1;i<=N;i++)
		for (j=1;j<=N;j++)
			dist[i][j]=adjm[i][j];
	for (k=1;k<=N;k++)
	{
		if (k==S || k==T) continue;
		for (i=1;i<=N;i++)
		{
			if (i==T) continue;
			for (j=1;j<=N;j++)
			{
				if (j==S) continue;
				if (dist[i][k]+dist[k][j]<dist[i][j])
					dist[i][j]=dist[i][k]+dist[k][j];
			}
		}
	}
	i=S;
	for (j=1;j<=N;j++)
		if (i!=j && i!=T && j!=S && dist[i][j]!=INF)
		{
			k=farest[j];
			if (j==T) k=0;
			if (dist[i][j] + k>dia)
				dia=dist[i][j] + k;
		}
}
void solve()
{
	for (int i=1;i<=K;i++)
	{
		S=mapping[P[i].s];T=mapping[P[i].t];
		dia=0;
		floyd();
		int last=dia+P[i].stime;
		if (last>QuestTime)
			Ans++;
	}
}
int main()
{
	init();
	solve();
	printf("%d",Ans);
	return 0;
}