Bellman-Ford..

题解的代码看的吓死了。。害怕
个人觉得写的挺精简的=v=+
c++
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <cstring>
#include <ctime>
#include <vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
int poi[100001],alr[10001],q[1000001],nxt[100001],f[10001],v[100001],dist[10001],ans[10001];
int n,m,s,x,y,z,cnt;
bool flag,vis[10001],inq[10001];
inline void add(int x,int y,int z)
{
poi[++cnt]=y;nxt[cnt]=f[x];v[cnt]=z;f[x]=cnt;
}
bool spfa(int x)
{
For(i,1,n) alr[i]=inq[i]=0;
alr[x]=1;q[1]=x;inq[x]=1;
dist[x]=0;
int l=1,r=1;
while(l<=r)
{
int t=q[l];inq[t]=0;
if(dist[x]<0) return 0;
for(int i=f[t];i;i=nxt[i])
{
int p=poi[i];
if(vis[p]) continue;
if(dist[p]<=dist[t]+v[i]) continue;
if(!inq[p])
{
q[++r]=p,inq[p]=1,alr[p]++;
if(alr[p]>n) return 0;
}
dist[p]=dist[t]+v[i];
}
l++;
}
For(i,1,n) vis[i]|=alr[i];
return 1;
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
For(i,1,m)
scanf("%d%d%d",&x,&y,&z),add(x,y,z);
For(i,1,n) dist[i]=ans[i]=1e9;
flag=1;
For(i,1,n) if(!vis[i]) flag&=spfa(i);
if(!flag)
{
puts("-1");
return 0;
}
memset(vis,0,sizeof vis);
For(i,1,n) dist[i]=1e9;
spfa(s);
For(i,1,n)
if(dist[i]==1e9)puts("NoPath");else printf("%d\n",dist[i]);
}


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long queue[1001],a[1001],psum[1001],dis[1001],l[1001][1001],cost[1001][1001];
long n,m,s,i,j;
bool hash[1001],bk;
void spfa(int s)
{
int head,tail,start,now,i;
for (i=1;i<=n;i++)
{
dis[i]=0xfffffff;
psum[i]=0;
hash[i]=false;
}
head=tail=1;hash[s]=true;
psum[s]=1;dis[s]=0;queue[1]=s;
while (head<=tail)
{
start=queue[(head-1)%n+1];
hash[start]=true;
for (i=1;i<=l[start][0];i++)
{
now=l[start][i];
if (dis[now]>dis[start]+cost[start][now])
{
dis[now]=dis[start]+cost[start][now];
if (!hash[now])
{
hash[now]=true;
tail++;
queue[(tail-1)%n+1]=now;
psum[now]++;
if (psum[now]>n)
{//记录每个点进队的次数(判断环的关键}
bk=false;
return;
}
}
}
}
head++;
hash[start]=false;
if (dis[s]<0)
{//判断环的一个优化
bk=false;
return;
}
}
}
void output()
{
bk=true;
spfa(s);
if (!bk)
{
printf("-1\n");
return;
}
memcpy(a,dis,sizeof(long)*(n+1));
for (i=1;i<=n;i++)
if (a[i]==0xfffffff)
{
bk=true;
spfa(i);
if (!bk)
{
printf("-1\n");
return;
}
}
for (i=1;i<=n;i++)
if (a[i]==0xfffffff) printf("NoPath\n");
else printf("%d\n",a[i]);
}
void input()
{
scanf("%d%d%d",&n,&m,&s);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i==j) cost[i][j]=0;
else cost[i][j]=0xfffffff;
memset(l,0,sizeof(l));
int x,y,c;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&c);
if (c<cost[x][y])
{
cost[x][y]=c;
l[x][0]++;
l[x][l[x][0]]=y;
}
}
}
int main()
{
input();
output();
system("pause");
return 0;
}

printf("-1");
就能过#2#3#4#5

本题及其坑爹！到处都是坑！乍一看是道SPFA裸题，但其实没那么简单。
Warning!
当输入的图不是连通图时，SPFA(Source)能做的就只是找出源点Source所在的连通分量中的负环而已。也就是说如果图中***存在环***，但不在***源点所在的连通分量内***的话，就会输出一堆的NoPath，而不是－1，从此WA没救。
解决方案：
添加一个数组***vis***，来确定某个点是否访问过（因为如果不在**源点的连通分量内**的点在SPFA的过程中时不会访问到的）。
然后每一个没有访问过的点都来一遍SPFA，以此来检查是否存在负环。
每次SPFA完了之后再将*每个*在***这一次SPFA中*** 访问过的点的vis设为true，判断的*标准*：是否进入过队列。

小优化：
dist［source］< 0 那么就存在负环，因为dist［source］本来为0，结果跑了一圈成负的了，那说明有负环。

#Block Code
#include <cstdio>
#include <cstring>
#include <queue>
#include <list>
#include <deque>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const long long Inf = 0x7F7F7F7F7F7F7F7FLL;
const int MaxV = 1005, MaxE = 100010;

struct _edge {
int to, next;
long long weit;
_edge() {to = next = -1; weit = 0;}
} edges[MaxE];

int numE, numV, idx = 0;
int cntInQ[MaxV], head[MaxV];
bool inQ[MaxV], vis[MaxV];
long long dist[MaxV];
queue<int> q;

bool SPFA(const int &sors) {
while (!q.empty()) q.pop();
fill(cntInQ, cntInQ + numV + 1, 0);
memset(inQ, 0, sizeof(inQ)); fill(dist, dist + numV + 1, Inf);
dist[sors] = 0;
q.push(sors); inQ[sors] = true; cntInQ[sors]++;
while (!q.empty()) {
int u = q.front(); q.pop();
inQ[u] = false;
if (dist[sors] < 0) return false;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to; long long w = edges[i].weit;
if (vis[v]) continue;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
q.push(v); inQ[v] = true;
if (++cntInQ[v] > numV)
return false;
}
}
}
for (int i = 1; i <= numV; i++) vis[i] = cntInQ[i] || vis[i];
return true;
}

void addEdge(int &u, int &v, long long &w) {
_edge &e = edges[idx];
e.to = v; e.weit = w; e.next = head[u];
head[u] = idx;
}

int main() {
// freopen("input.txt", "r", stdin);
int S, u, v;
long long w;
scanf("%d%d%d", &numV, &numE, &S);
fill(head, head + numV + 1, -1); fill(vis, vis + numV + 1, 0);
for (idx = 0; idx < numE; idx++) {
scanf("%d%d%lld", &u, &v, &w);
addEdge(u, v, w);
}
for (int i = 1; i <= numV; i++) {
if (vis[i]) continue;
if (!SPFA(i)) {
printf("-1\n");
exit(0);
}
}
memset(vis, 0, sizeof(vis));
SPFA(S);
for (int i = 1; i <= numV; i++)
if (dist[i] != Inf)
printf("%lld\n", dist[i]);
else
printf("NoPath\n");
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 16476 KiB, score = 0
测试数据 #1: Accepted, time = 15 ms, mem = 16480 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 16484 KiB, score = 15
测试数据 #3: Accepted, time = 15 ms, mem = 16484 KiB, score = 15
测试数据 #4: Accepted, time = 46 ms, mem = 16484 KiB, score = 20
测试数据 #5: Accepted, time = 62 ms, mem = 16484 KiB, score = 25
测试数据 #6: Accepted, time = 78 ms, mem = 16480 KiB, score = 15
Accepted, time = 216 ms, mem = 16484 KiB, score = 100
代码
type
tlist=packed array[0..1010,0..1010] of int64;
var a:tlist;
b:tlist;
c:array[0..1010] of int64;
d:array[0..10000] of longint;
e:array[0..1010] of boolean;
x,y,n,m,w,j:int64;
i,k:longint;
procedure spfa;
var now,i:longint;
begin
while n<=m do
begin
now:=d[n];
for i:=1 to b[now,0] do
if c[b[now,i]]>c[now]+a[now,b[now,i]] then
begin
c[b[now,i]]:=c[now]+a[now,b[now,i]];
if e[b[now,i]] then
begin
inc(m);
d[m]:=b[now,i];
e[b[now,i]]:=false;
end;
end;
e[now]:=true;
inc(n);
if n>y*4 then
begin
writeln(-1);
halt;
end;
end;
end;
begin
read(n,m,j);
for i:=1 to m do
begin
read(x,y,w);
if (a[x,y]=0)or(a[x,y]>w) then
begin
inc(b[x,0]);
b[x,b[x,0]]:=y;
a[x,y]:=w;
end;
end;
x:=j;
y:=n;
randomize;
while k<>2 do
begin
inc(k);
if k=1 then x:=trunc(random(y)+1) else x:=j;
fillchar(e,sizeof(e),true);
fillchar(d,sizeof(d),0);
fillchar(c,sizeof(c),275);
c[x]:=0;
d[1]:=x;
e[x]:=false;
n:=1;
m:=1;
spfa;
end;
for i:=1 to y do
if c[i]<>1374463283923456787 then writeln(c[i]) else writeln('NoPath');
end.
因为有未联通边出现负环，所以用个随机判负环，然后再从S进行SPFA，就AC了。

测试数据 #0: Accepted, time = 0 ms, mem = 21684 KiB, score = 0
测试数据 #1: Accepted, time = 15 ms, mem = 21680 KiB, score = 10
测试数据 #2: Accepted, time = 21 ms, mem = 21680 KiB, score = 15
测试数据 #3: Accepted, time = 93 ms, mem = 21676 KiB, score = 15
测试数据 #4: Accepted, time = 593 ms, mem = 21684 KiB, score = 20
测试数据 #5: Accepted, time = 337 ms, mem = 21684 KiB, score = 25
测试数据 #6: WrongAnswer, time = 93 ms, mem = 21684 KiB, score = 0
WrongAnswer, time = 1152 ms, mem = 21684 KiB, score = 85
代码
type
edge=record
f,t,v:longint;
end;
var n,m,i,j,u,x,vvv,s:longint;
t,head:array[0..10001] of longint;
q:array[0..5000001] of longint;
dist:array[0..10001] of int64;
e:array[0..100001] of edge;
v,vv:array[0..10001] of boolean;
procedure spfa(x:longint);
var i,nowe,now,l,r:longint;
begin
if vv[x] then vv[x]:=false
else exit;
fillchar(v,sizeof(v),true);
fillchar(t,sizeof(t),0);
l:=1; r:=1; q[1]:=x;
for i:=1 to n do dist[i]:=1000000000000000;
dist[x]:=0; v[1]:=false;
while l<=r do
begin
now:=q[l];
nowe:=head[now];
while nowe<>0 do
begin
//writeln(dist[e[nowe].t],' ',dist[now]+e[nowe].v);
if dist[e[nowe].t]>dist[now]+e[nowe].v then
begin
dist[e[nowe].t]:=dist[now]+e[nowe].v;
if (v[e[nowe].t]) and (t[e[nowe].t]<n/3) then begin
inc(r);
vv[e[nowe].t]:=false;
q[r]:=e[nowe].t;
inc(t[q[r]]);
v[q[r]]:=false;
end
else if (v[e[nowe].t]) and (t[e[nowe].t]>=n/3) then
begin
writeln(-1);
halt;
end;
end;
nowe:=e[nowe].f;
end;
v[now]:=true;
inc(l);
end;
end;
begin
readln(n,m,s);
for i:=1 to m do
begin
readln(u,x,vvv);
e[i].t:=x;
e[i].v:=vvv;
e[i].f:=head[u];
head[u]:=i;
end;
fillchar(vv,sizeof(vv),true);
for i:=1 to n do if s<>i then spfa(i);
fillchar(vv,sizeof(vv),true);
spfa(s);
for i:=1 to n do
begin
if dist[i]<>1000000000000000 then writeln(dist[i])
else writeln('NoPath');
end;
end.
最后一个点 WA 但数据输上去 貌似和答案一样啊。。求大牛

测试数据 #0: Accepted, time = 15 ms, mem = 3236 KiB, score = 0
测试数据 #1: Accepted, time = 15 ms, mem = 3232 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 3232 KiB, score = 15
测试数据 #3: Accepted, time = 686 ms, mem = 5444 KiB, score = 15
测试数据 #4: Accepted, time = 998 ms, mem = 6576 KiB, score = 20
测试数据 #5: Accepted, time = 265 ms, mem = 3528 KiB, score = 25
测试数据 #6: Accepted, time = 93 ms, mem = 3232 KiB, score = 15
Accepted, time = 2118 ms, mem = 6576 KiB, score = 100

第四个点什么鬼。。。只要998