Dijkstra，每次松弛时更新路径数组
话说同样一份代码，关同步的cincout有四个点TLE，改成scanf和printf之后时间变成了原来的1/4，我记得两者的速度差别不是不大么……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF = 0x7FFFFFFF;
const int MAXN = 1011;
struct Node
{
int d;
int u;
bool operator< (const Node &rhs) const
{
return d > rhs.d;
}
};
struct Edge
{
int from, to, dis;
};
struct Dijkstra
{
int n, m;
vector<int> g[MAXN];
vector<int> path[MAXN];
vector<Edge> edge;
int d[MAXN];
bool vis[MAXN];
void init(int n)
{
this->n = n;
for(int i = 0; i < MAXN; ++i)
{
g[i].clear();
path[i].clear();
}
edge.clear();
}
void AddEdge(int from ,int to, int dis)
{
edge.push_back((Edge){from, to, dis});
m = edge.size();
g[from].push_back(m - 1);
}
void dijkstra(int s)
{
priority_queue<Node> q;
fill(d, d + n + 1, INF);
memset(vis, 0, sizeof(vis));
q.push((Node){0, s});
d[s] = 0;
path[s].push_back(s);
while(!q.empty())
{
Node cur = q.top(); q.pop();
int u = cur.u;
if(vis[u])continue;
vis[u] = 1;
for(int i = 0; i < g[u].size(); ++i)
{
Edge &e = edge[g[u][i]];
if(d[e.to] > d[u] + e.dis)
{
d[e.to] = d[u] + e.dis;
path[e.to].clear();
for(int i = 0; i < path[u].size(); ++i)
path[e.to].push_back(path[u][i]);
path[e.to].push_back(e.to);
q.push((Node){d[e.to], e.to});
}
}
}
}
}dijks;
int n;
int main()
{
scanf("%d", &n);
dijks.init(n);
int tdis;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
{
scanf("%d", &tdis);
if(tdis == 0)continue;
dijks.AddEdge(i, j, tdis);
}
dijks.dijkstra(0);
vector<int> &p = dijks.path[n - 1];
bool first = 1;
for(int i = 0; i < p.size(); ++i)
{
if(first)
{
first = 0;
printf("%d", p[i] + 1);
}
else printf(" %d", p[i] + 1);
}
printf("\n");
printf("%d\n", dijks.d[n - 1]);
return 0;
}

测试数据 #0: Accepted, time = 62 ms, mem = 4540 KiB, score = 15
测试数据 #1: Accepted, time = 140 ms, mem = 4544 KiB, score = 15
测试数据 #2: Accepted, time = 15 ms, mem = 4544 KiB, score = 15
测试数据 #3: Accepted, time = 156 ms, mem = 4540 KiB, score = 15
测试数据 #4: Accepted, time = 15 ms, mem = 4540 KiB, score = 15
测试数据 #5: Accepted, time = 109 ms, mem = 4548 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 4544 KiB, score = 5
测试数据 #7: Accepted, time = 15 ms, mem = 4544 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 4544 KiB, score = 5
测试数据 #9: Accepted, time = 109 ms, mem = 4544 KiB, score = 5
Accepted, time = 636 ms, mem = 4548 KiB, score = 100
####代码
program connection;
var
a:array[1..1000,1..1000] of longint;
v:array[1..1000] of boolean;
prev,dist,temp:array[1..1000] of longint;
min:longint;
n,i,j,l,tmp:integer;
f:boolean;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(a[i,j]);
if (a[i,j]>0) and (i=1) then dist[j]:=a[i,j] else dist[j]:=maxlongint;
end;
if i=1 then prev[i]:=-1 else prev[i]:=1;
readln;
end;
fillchar(v,sizeof(v),true);
fillchar(temp,sizeof(temp),0);
dist[1]:=0;v[1]:=false;
repeat
min:=maxlongint;l:=1;//Question
for i:=1 to n do if v[i] and (dist[i]<min) then begin min:=dist[i];l:=i;end;
v[l]:=false;
for i:=1 to n do if (a[l,i]>0) and (dist[l]+a[l,i]<dist[i]) then begin dist[i]:=dist[l]+a[l,i];prev[i]:=l;end;
f:=true;
for i:=1 to n do if v[i] then begin f:=false;break;end;
until f;
tmp:=n;i:=1;
while prev[tmp]<>-1 do
begin
temp[i]:=prev[tmp];
i:=i+1;
tmp:=prev[tmp];
end;
for j:=i-1 downto 1 do write(temp[j],' ');
writeln(n);
writeln(dist[n]);
end.
用Dijkstra求最短路径即可，但要加入prev数组记录最短路径节点。
请教各位大神：程序中打Question的语句中为什么一定要l:=1;呢？我之前置l为0或不赋初始值都WA了，胡乱调试时令l=1就AC了。**求解释！！！**

var n,i,j,tot:longint;
a:array[0..1001,0..1001] of longint;
f:array[0..1001] of int64;
b:array[0..1001] of longint;
function min(x,y:int64):int64;
begin
if x<y then exit(x) else exit(y);
end;
begin
assign(input,'input10.txt');assign(output,'output.txt');
reset(input);rewrite(output);
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
read(a[i,j]);
readln;
end;
for i:=1 to n do f[i]:=maxlongint;
f[1]:=0;
for i:=2 to n do
for j:=1 to i-1 do
if a[j,i]<>0 then
f[i]:=min(f[i],f[j]+a[j,i]);
tot:=1;b[tot]:=n;
for i:=n-1 downto 1 do
if f[i]+a[i,n]=f[n] then
begin
inc(tot);b[tot]:=i;n:=i;
end;
for i:=tot downto 1 do write(b[i],' ');
writeln;
writeln(f[b[1]]);
close(input);close(output);
end.

spfa

测试数据 #0: Accepted, time = 124 ms, mem = 11996 KiB, score = 15
测试数据 #1: Accepted, time = 265 ms, mem = 11988 KiB, score = 15
测试数据 #2: Accepted, time = 15 ms, mem = 11996 KiB, score = 15
测试数据 #3: Accepted, time = 218 ms, mem = 11992 KiB, score = 15
测试数据 #4: Accepted, time = 0 ms, mem = 11988 KiB, score = 15
测试数据 #5: Accepted, time = 202 ms, mem = 11992 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 11988 KiB, score = 5
测试数据 #7: Accepted, time = 31 ms, mem = 11996 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 11992 KiB, score = 5
测试数据 #9: Accepted, time = 156 ms, mem = 11992 KiB, score = 5
Accepted, time = 1026 ms, mem = 11996 KiB, score = 100

代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define N 1000

struct edge{
int u,v,w;
};

struct point{
int val;
int in;
int from;
};

struct edge edge[N*(N-1)];
int u_index[N+1];
int edge_r;
struct point point[N];
int stack[N],rear,front;
int n,m;

void push_on(int num,int val,int from)
{
point[num].val = val;
point[num].from = from;
if (!point[num].in) {
point[num].in = 1;
stack[rear++%N] = num;
}
}

void out_stack()
{
point[stack[front++%N]].in = 0;
}

void add_edge(int u,int v,int w)
{
edge[edge_r].u = u;
edge[edge_r].v = v;
edge[edge_r++].w = w;
}

void set_index(int rear)
{
int i,u;
i = 0; u = 0;
while (u <= n) {
while (i < rear)
if (edge[i].u < u)
i++;
else
break;
u_index[u++] = i;
}
}

void base_point()
{
int i,tmp;
tmp = (1<<31)-1;
front = rear = 0;
for (i = 0;i < n;i++) point[i].in = 0;
push_on(0,0,-1);
for (i = 1;i < n;i++)
push_on(i,tmp,-1);
}

void init()
{
int i,j,dis;
scanf("%d",&n); m = n;
edge_r = 0;
for (i = 0;i < n;i++) {
for (j = 0;j < m;j++) {
scanf("%d",&dis);
if (dis)
add_edge(i,j,dis);
}
}
set_index(edge_r);
base_point();
}

void spfa()
{
int u,i,t,v;
while (front < rear) {
u = stack[front%N];
for (i = u_index[u];i < u_index[u+1];i++) {
v = edge[i].v;
if (point[v].val > (t = point[u].val+edge[i].w))
push_on(v,t,u);
}
out_stack();
}
}

void print_path()
{
int rear,stack[N],v;
rear = 0;
v = stack[rear++] = n-1;
while (point[v].from != -1)
v = stack[rear++] =point[v].from;
while (rear > 0)
printf("%d ",stack[--rear]+1);
printf("\n");
}

int main()
{
init();
spfa();
print_path();
printf("%d\n",point[n-1].val);
return 0;
}

评测结果
编译成功

foo.c: In function 'main':
foo.c:86:1: warning: control reaches end of non-void function [-Wreturn-type]
foo.c:46:11: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
测试数据 #0: Accepted, time = 124 ms, mem = 4408 KiB, score = 15
测试数据 #1: Accepted, time = 218 ms, mem = 4404 KiB, score = 15
测试数据 #2: Accepted, time = 0 ms, mem = 4412 KiB, score = 15
测试数据 #3: Accepted, time = 156 ms, mem = 4408 KiB, score = 15
测试数据 #4: Accepted, time = 31 ms, mem = 4408 KiB, score = 15
测试数据 #5: Accepted, time = 249 ms, mem = 4412 KiB, score = 5
测试数据 #6: Accepted, time = 15 ms, mem = 4408 KiB, score = 5
测试数据 #7: Accepted, time = 31 ms, mem = 4408 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 4408 KiB, score = 5
测试数据 #9: Accepted, time = 249 ms, mem = 4412 KiB, score = 5
Accepted, time = 1088 ms, mem = 4412 KiB, score = 100
代码
#include<stdio.h>
#define M 199999999

int n,way[1005][1005],plan[1005],flag[1005],pre[1005],ans[1000];

int main()
{
// freopen("1635.in","r",stdin);
int i,j,k,mn,min;
scanf("%d",&n);
k=n-2;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&way[i][j]);
if(!way[i][j])
{
way[i][j]=M;
}
}
}
for(i=1;i<=n;i++)
{
plan[i]=way[1][i];
pre[i]=1;
}

while(k)
{
k--;min=M;

for(i=2;i<=n;i++)
{
if(flag[i])
{
continue;
}

if(min>plan[i])
{
min=plan[i];
mn=i;
}
}
flag[mn]=1;

for(i=2;i<=n;i++)
{
if(flag[i])
{
continue;
}

if(plan[i]>plan[mn]+way[mn][i])
{
plan[i]=plan[mn]+way[mn][i];
pre[i]=mn;
}
}
}
int tt=n;
ans[1]=tt;
for(i=2;i<=1000;i++)
{
tt=pre[tt];
ans[i]=tt;
if(tt==1)
{
break;
}
}
for(;i;i--)
{
printf("%d",ans[i]);
if(i!=1)
{
printf(" ");
}
else
{
printf("\n");
}
}
printf("%d\n",plan[n]);
}

评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:19:10: warning: unused variable 'k' [-Wunused-variable]
foo.cpp:19:12: warning: unused variable 'mn' [-Wunused-variable]
foo.cpp:19:15: warning: unused variable 'min' [-Wunused-variable]
测试数据 #0: WrongAnswer, time = 109 ms, mem = 4412 KiB, score = 0
测试数据 #1: WrongAnswer, time = 312 ms, mem = 4404 KiB, score = 0
测试数据 #2: WrongAnswer, time = 0 ms, mem = 4412 KiB, score = 0
测试数据 #3: WrongAnswer, time = 171 ms, mem = 4408 KiB, score = 0
测试数据 #4: Accepted, time = 15 ms, mem = 4412 KiB, score = 15
测试数据 #5: WrongAnswer, time = 140 ms, mem = 4412 KiB, score = 0
测试数据 #6: Accepted, time = 0 ms, mem = 4412 KiB, score = 5
测试数据 #7: WrongAnswer, time = 31 ms, mem = 4416 KiB, score = 0
测试数据 #8: WrongAnswer, time = 31 ms, mem = 4408 KiB, score = 0
测试数据 #9: WrongAnswer, time = 234 ms, mem = 4412 KiB, score = 0
WrongAnswer, time = 1043 ms, mem = 4416 KiB, score = 20
代码
#include<stdio.h>
#define M 199999999
int n,way[1005][1005],plan[1005],q[1010],pre[1005],ans[1005];

int ii(int x)
{
for(int i=0;i<n;i++)
{
if(q[i]==x)
{
return 1;
}
}
return 0;
}

int main()
{
int i,j,k,mn,min;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&way[i][j]);
if(!way[i][j])
{
way[i][j]=M;
}
}
plan[i]=M;
pre[i]=1;
}
plan[1]=0;
q[0]=1;int tn=1,tp=0;
while(tn)
{
tn--;
int t=q[tn];
for(i=1;i<=n;i++)
{
if(plan[t]+way[t][i]<plan[i])
{
plan[i]=plan[t]+way[t][i];
pre[i]=t;
if(!ii(i))
{
tp=(tp+1)%(n+5);
tn++;
q[tp]=i;
}
}
}
}
int tt=n;
ans[1]=tt;
for(i=2;i<=1000;i++)
{
tt=pre[tt];
ans[i]=tt;
if(tt==1)
{
break;
}
}
for(;i;i--)
{
printf("%d",ans[i]);
if(i!=1)
{
printf(" ");
}
else
{
printf("\n");
}
}
printf("%d\n",plan[n]);
}

为毛这么吊？
7
0 32 56 0 0 0 0
0 0 0 64 8 55 0
0 6 6 0 44 12 6
15 6 0 0 0 0 4
0 0 12 8 0 32 7
0 0 0 0 0 0 11
0 0 0 0 0 5 0

WA掉的代码过了，A掉的代码错了，哇咧，为毛这么吊？

var
map:array[0..1000,0..1000] of longint;
dis,pre:array[0..1000] of longint;
flag:array[0..1000] of boolean;
x,i,j,n,k:longint;
procedure try(k:longint);
begin
if k=1 then
begin
write(1,' ');
exit;
end;
try(pre[k]);
write(k,' ');
end;
begin
readln(n);
fillchar(map,sizeof(map),\(7f);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(x);
if x>0 then map[i,j]:=x;
end;
readln;
end;
fillchar(dis,sizeof(dis),\)7f);
dis[1]:=0;
while true do
begin
k:=0;
for i:=1 to n do
if not(flag[i]) and (dis[i]<dis[k]) then k:=i;
flag[k]:=true;
if k=0 then break;
for i:=1 to n do
if dis[k]+map[k,i]<dis[i] then
begin
dis[i]:=dis[k]+map[k,i];
pre[i]:=k;
end;
end;
try(n);
writeln;
writeln(dis[n]);
end.
明显的，n^2
边这么多，老迪比老S更优。
当然，要加一个pre记录路径，递归输出。
PS：明天NOIP复赛，虽说普及组不考图论，但我还是练练手。

floyd改单源？处理路径有点麻烦。。。
var f:array[0..1000,0..1000]of longint;i,j,k,n:longint;w:array[0..1000,0..1000]of longint;way:array[0..1000]of longint;len:longint;
procedure printf(n:longint);
begin
if w[1,n]=0 then begin inc(len,1);way[len]:=n;exit;end;
inc(len,1);
way[len]:=n;
printf(w[1,n]);
end;
begin
len:=0;
fillchar(w,sizeof(w),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(f[i,j]);
if f[i,j]=0 then f[i,j]:=maxint;
end;
for j:=1 to n do
for k:=1 to n do
if (j<>k) then if f[1,k]+f[k,j]<f[1,j] then begin f[1,j]:=f[1,k]+f[k,j];w[1,j]:=k;end;
printf(n);
write(1,' ');
for i:=len downto 1 do write(way[i],' ');
writeln;
writeln(f[1,n]);
end.

对这种程序能Ac表示无语。（某位大神说这程序有问题）

#include<cstdio>
struct gmh
{
int dis,fa;
}f[2008];
int n,min,p=0,a[2008],way[2008];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
scanf("%d",&a[j]);
if (a[j])
if (f[j].dis==0 || f[j].dis>a[j]+f[i].dis)
{
f[j].dis=a[j]+f[i].dis;
f[j].fa=i;
}
}
for (int i=n;i;i=f[i].fa)
{
p++;
way[p]=i;
}
for (int i=p;i>=1;i--)
printf("%d ",way[i]);
printf("\n%d",f[n].dis);
return 0;
}

var
a:array[0..1000,0..1000] of longint;
b:array[1..1000,1..1000] of longint;
dis:array[1..1000] of longint;
pd:array[1..1000] of boolean;
lb:array[1..1000] of longint;
times:array[1..1000] of longint;
q,d:array[1..1000] of longint;
tot,i,j,k,n,m,x,y,z,h,t:longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(b[i,j]);
if b[i,j]<>0 then
begin
inc(a[i,0]);a[i,a[i,0]]:=j;
end;
end;
dis[1]:=0; h:=0;t:=1;lb[1]:=1;
for i:=2 to n do dis[i]:=maxlongint;
while h<t do
begin
inc(h);
x:=lb[h];
for i:=1 to a[x,0] do
if dis[a[x,i]]>dis[x]+b[x,a[x,i]] then
begin
dis[a[x,i]]:=dis[x]+b[x,a[x,i]];
q[a[x,i]]:=x;
if not pd[a[x,i]] then
begin
inc(t);
lb[t]:=a[x,i];
inc(times[a[x,i]]);
pd[a[x,i]]:=true;
end;
end;
pd[x]:=false;
end;
k:=n;
while k>1 do
begin
inc(tot);
d[tot]:=k;
k:=q[k];
end;
write(1,' ');
for i:=tot downto 2 do write(d[i],' '); writeln(d[1]);
writeln(dis[n]);
end.

###Block Code
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

// GRAPH [Directed!]
#define allocint(x,sz) {x=new int[sz];}
class adjGraph
{
public:
int n,m;
int* firstlnk;
int* lnknext,*lnkto,*lnkfro,*lnkw;
adjGraph()
{
n=0;
m=0;
firstlnk=lnknext=lnkto=lnkfro=lnkw=NULL;
}
~adjGraph()
{
if(n!=0&&m!=0)
{
delete firstlnk;
delete lnkto;
delete lnkfro;
delete lnknext;
delete lnkw;
}
}
inline std::istream& input(std::istream& in)
{
int r,t,cur=0;
in>>n;
m=n*n;
allocint(firstlnk,n);
allocint(lnkto,m);
allocint(lnkfro,m);
allocint(lnkw,m);
allocint(lnknext,m);
memset(firstlnk,-1,n*sizeof(int));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
in>>r;
if(r!=0)
{
t=firstlnk[i];
firstlnk[i]=cur;
lnknext[cur]=t;
lnkto[cur]=j;
lnkfro[cur]=i;
lnkw[cur]=r;
cur++;
}
}
m=cur;
return in;
}
};
#define INF 1000000
adjGraph base;

// Dijkstra-------------------NOT SO FAMILIAR !
int start;
int end;
int* father;
int* d; //!!! NO NEED FOR the second dimension
bool* visited;
inline void init(int fro)
{
d=new int[base.n];
visited=new bool[base.n];
father=new int[base.n];
for(int i=0;i<base.n;i++)
d[i]=INF,visited[i]=false,father[i]=-1; //!!!! DON'T use lnkw to init d[]
d[fro]=0;
}
inline int getsmallp()
{
int ans=-1;
for(int i=0;i<base.n;i++)
if(!visited[i]) //!!!! SET here as the place to check VISITED[] is more efficient
{
if(ans==-1) ans=i;
else ans=(d[ans]>d[i])?i:ans;
}
return ans;
}
void Dijkstra(int fro)
{
init(fro);
for(int i=0;i<base.n;i++)
{
int now=getsmallp();
int t=base.firstlnk[now];
visited[now]=true;
while(t!=-1)
{
int u=base.lnkto[t];
int w=base.lnkw[t];
if(d[u]>d[now]+w)
{
d[u]=d[now]+w;
/* !!!!!!!!!!!!!!! VERY !!!!!!!!!!!!!!!!!!! IMPORTANT !!!!!!!!!!
if(father[u]==-1)
father[u]=now;
else father[u]=(father[u]>now)?now:father[u];*/
father[u]=now;
}
t=base.lnknext[t];
}
}

stack<int> help;
help.push(end);
int t=father[end];
while(t!=-1)
{
help.push(t);
t=father[t];
}
while(!help.empty())
{
t=help.top();help.pop();
cout<<t+1<<' ';
}
cout<<endl<<d[end]<<endl;
}

int main()
{
cin.sync_with_stdio(false);
base.input(cin);
start=0;end=base.n-1;
Dijkstra(start);
return 0;
}

Dijkstra总算通过了，积累了一些经验。

Jtwd2 via JudgeDaemon2/13.7.4.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 249 ms, mem = 6340 KiB, score = 15
测试数据 #1: Accepted, time = 655 ms, mem = 16144 KiB, score = 15
测试数据 #2: Accepted, time = 15 ms, mem = 684 KiB, score = 15
测试数据 #3: Accepted, time = 686 ms, mem = 15916 KiB, score = 15
测试数据 #4: Accepted, time = 46 ms, mem = 1092 KiB, score = 15
测试数据 #5: Accepted, time = 561 ms, mem = 13848 KiB, score = 5
测试数据 #6: Accepted, time = 15 ms, mem = 824 KiB, score = 5
测试数据 #7: Accepted, time = 93 ms, mem = 2848 KiB, score = 5
测试数据 #8: Accepted, time = 31 ms, mem = 1188 KiB, score = 5
测试数据 #9: Accepted, time = 530 ms, mem = 12548 KiB, score = 5
Accepted, time = 2881 ms, mem = 16144 KiB, score = 100

###Block Code
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

// GRAPH [Directed!]
#define allocint(x,sz) {x=new int[sz];}
class adjGraph
{
public:
int n,m;
int* firstlnk;
int* lnknext,*lnkto,*lnkfro,*lnkw;
adjGraph()
{
n=0;
m=0;
firstlnk=lnknext=lnkto=lnkfro=lnkw=NULL;
}
~adjGraph()
{
if(n!=0&&m!=0)
{
delete firstlnk;
delete lnkto;
delete lnkfro;
delete lnknext;
delete lnkw;
}
}
inline std::istream& input(std::istream& in)
{
int r,t,cur=0;
in>>n;
m=n*n;
allocint(firstlnk,n);
allocint(lnkto,m);
allocint(lnkfro,m);
allocint(lnkw,m);
allocint(lnknext,m);
memset(firstlnk,-1,n*sizeof(int));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
in>>r;
if(r!=0)
{
t=firstlnk[i];
firstlnk[i]=cur;
lnknext[cur]=t;
lnkto[cur]=j;
lnkfro[cur]=i;
lnkw[cur]=r;
cur++;
}
}
m=cur;
return in;
}
};
#define INF 1000000
adjGraph base;

// Dijkstra-------------------NOT SO FAMILIAR !
int start;
int end;
int* father;
int* d; //!!! NO NEED FOR the second dimension
bool* visited;
inline void init(int fro)
{
d=new int[base.n];
visited=new bool[base.n];
father=new int[base.n];
for(int i=0;i<base.n;i++)
d[i]=INF,visited[i]=false,father[i]=-1; //!!!! DON'T use lnkw to init d[]
d[fro]=0;
}
inline int getsmallp()
{
int ans=-1;
for(int i=0;i<base.n;i++)
if(!visited[i]) //!!!! SET here as the place to check VISITED[] is more efficient
{
if(ans==-1) ans=i;
else ans=(d[ans]>d[i])?i:ans;
}
return ans;
}
void Dijkstra(int fro)
{
init(fro);
for(int i=0;i<base.n;i++)
{
int now=getsmallp();
int t=base.firstlnk[now];
visited[now]=true;
while(t!=-1)
{
int u=base.lnkto[t];
int w=base.lnkw[t];
if(d[u]>d[now]+w)
{
d[u]=d[now]+w;
/* !!!!!!!!!!!!!!! VERY !!!!!!!!!!!!!!!!!!! IMPORTANT !!!!!!!!!!
if(father[u]==-1)
father[u]=now;
else father[u]=(father[u]>now)?now:father[u];*/
father[u]=now;
}
t=base.lnknext[t];
}
}

stack<int> help;
help.push(end);
int t=father[end];
while(t!=-1)
{
help.push(t);
t=father[t];
}
while(!help.empty())
{
t=help.top();help.pop();
cout<<t+1<<' ';
}
cout<<endl<<d[end]<<endl;
}

int main()
{
cin.sync_with_stdio(false);
base.input(cin);
start=0;end=base.n-1;
Dijkstra(start);
return 0;
}

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
struct P{
int s,t,val;
}data[1000005];
queue<int> QUE;
int P,a,b=1;
int S[2001],dis[2001],cnt,pre[2001];
void solve();
void print(int);
int main(){
freopen("1.in","r",stdin);
scanf("%d",&P);
for(int i=1;i<=P;i++)
for(int j=1;j<=P;j++){
scanf("%d",&a);
if(a!=0) data[b].s=i,data[b].t=j,data[b].val=a,S[i]++,b++;
}
for(int i=1;i<=b;i++) S[i]=b+1;
for(int i=b;i>0;i--) S[data[i].s]=i;
for(int i=0;i<=P;i++) if(S[i+1]==b+1) S[i+1]=S[i];
for(int i=1;i<=P;i++) dis[i]=0xfffffff;
int a;

a=1;
dis[a]=0;
QUE.push(a);
solve();
print(pre[P]);
printf("%d\n%d",P,dis[P]);

}
void print(int p)
{
if(p==0) return;
print(pre[p]);
printf("%d ",p);
}
void solve(){
while(!QUE.empty()){
int tmp=QUE.front();
QUE.pop();
for(int i=S[tmp];i<S[tmp+1];i++){
if(dis[data[i].t] > dis[tmp]+data[i].val)
dis[data[i].t]=dis[tmp]+data[i].val,pre[data[i].t]=tmp,QUE.push(data[i].t);
}
}
}
全部RE掉了 求解

求助大神 为什么都WA掉了呢
求数据范围

var i,j,n,s,t:longint;

　　a:array[0..1000,0..1000] of longint;

　　f,q:array[0..1000] of longint;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

read(a);

for i:=1 to n-1 do

f[i]:=maxlongint;

for i:=n-1 downto 1 do

for j:=i+1 to j do

begin

if (a>0) and (a+f[j]

var i,j,n,s,t:longint;

a:array[0..1000,0..1000] of longint;

f,q:array[0..1000] of longint;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

read(a);

for i:=1 to n-1 do

f[i]:=maxlongint;

for i:=n-1 downto 1 do

for j:=i+1 to j do

begin

if (a>0) and (a+f[j]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

唉，还得细心啊！！

floyed秒杀......

第一先输路径,第二是有向边,第三,任何时候都要细心,冷静。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 72ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：72ms

var q:array[0..100000]of longint;

b:array[0..1003]of boolean;

dis,route:array[0..1003]of longint;

a:array[0..1003,0..1003]of longint;

n,x,y,w,m:longint;

procedure init;

var i,j:longint;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

begin

read(a);

if a=0 then a:=99999999;

end;

end;

procedure find(k:longint);

begin

if k0 then

begin

find(route[k]);

write(k,' ');

end;

end;

procedure spfa;

var i,x,l,r:longint;

begin

q[1]:=1;

l:=1;

r:=1;

for i:=1 to n do route[i]:=0;

for i:=2 to n do dis[i]:=99999999;

dis[1]:=0;

fillchar(b,sizeof(b),false);

b[1]:=true;

while l

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 119ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：207ms

难得一次AC...好水的题...不过复习了一下DIJKSTRA的路径处理