PowderHan LV 10 @ 2017-05-04 08:13:10

Accepted
/in/foo.cc: In function 'void check()':
/in/foo.cc:127:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
if(!vis[i])
^

状态耗时内存占用

#1 Accepted 2ms 2.59MiB
#2 Accepted 6ms 2.582MiB
#3 Accepted 2ms 2.59MiB
#4 Accepted 5ms 2.715MiB
#5 Accepted 22ms 2.602MiB
#6 Accepted 18ms 2.625MiB
#7 Accepted 23ms 2.723MiB

好题啊
陷阱蛮多的Orz
提供了一些新的套路23333
第一眼看过去觉得是个SPFA裸题啊
后面感觉不对没这么简单
出题人黑良心
当输入的图不是连通图时，SPFA(s)能做的就只是找出源点s所在的连通分量中的负环而已。
也就是说如果图中存在环，但不在源点所在的连通分量内的话，就会输出一堆的NoPath，
而不是－1，从此WA没救。
解决方案：
添加一个数组vis，来确定某个点是否访问过
（因为如果不在源点的连通分量内的点在SPFA的过程中时不会访问到的）。
然后每一个没有访问过的点都来一遍SPFA，以此来检查是否存在负环。
每次SPFA完了之后再将每个在这一次SPFA中访问过的点的vis设为true，判断的标准：
是否进入过队列。
小优化：
dist［source］< 0 那么就存在负环，因为dist［source］本来为0，
结果跑了一圈成负的了，那说明有负环。
首先我们看到我们要先处理有没有负权环的问题
这个明显要独立做出来
就是我们先定一个vis数组标记点是否访问过
然后每次对于一个未访问的点
SPFA一下并在SPFA中把到过的点标记访问过
那么我们可以知道如果和这个点连通】
那么一定就是能走到(能标记到访问)
所以我们下一次就直接从没有访问过的点继续SPFA
即我们一次SPFA可以处理掉一个SCC中是否有负权环的问题
然后一直SPFA完所有的强连通分量
然后处理完后确定没有环了
我们就可以进行正常的SPFA求出最短路了
Orz因为怕麻烦啊
SPFA两种(一种要用到vis一种不要用到vis)就合在一起了
所以检查完负权环后
就要将vis数组清为0防止被SPFA中的判断vis误伤啊
然后就可以直接暴力做了
裸的SPFA好激动啊
注意一下这里SPFA中的小优化
上面也说了
嗯挺好用的Orz
好题
处理负权边和不连通问题
QAQ
随便读入优化一下飞快

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

char rd;    int pn;
template<typename Type>
inline void read(Type& v)
{
    pn=1;
    while((rd=getchar())<'0'||rd>'9')
        if(rd=='-')
            pn=-1;
    v=rd-'0';
    while((rd=getchar())>='0'&&rd<='9')
        v=v*10+rd-'0';
    v*=pn;
}
template<typename Type>
inline void out(Type v,bool c=1)
{
    if(v==0)
        putchar(48);
    else  
    {
        if(v<0)
        {
            putchar('-');
            v=-v;
        }
        int len=0,dg[20];  
        while(v>0)
        {
            dg[++len]=v%10;
            v/=10;
        }  
        for(int i=len;i>=1;i--)
            putchar(dg[i]+48);  
    }
    if(c)
        putchar('\n');
    else
        putchar(' ');
}

const int MAXN=1005;
const int MAXM=200005;
const int INF=0x7fffffff;
struct Edge
{
    int to,w,nxt;
    Edge()
    {
        to=nxt=-1;
        w=0;
    }
}e[MAXM];
int fisrt[MAXN];
int tot;
int n,m,s;

inline void Add_Edge(int u,int v,int w)
{
    e[++tot].to=v;  e[tot].w=w;
    e[tot].nxt=fisrt[u];    fisrt[u]=tot;
}

void init()
{
    memset(fisrt,-1,sizeof(fisrt));
    read(n);    read(m);    read(s);
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        read(u);    read(v);    read(w);
        Add_Edge(u,v,w);
    }
}

bool vis[MAXN],inq[MAXN];
int cnt[MAXN];
int dis[MAXN];
queue<int> q;

bool spfa(int s)
{
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    memset(inq,0,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    while(!q.empty())
        q.pop();
    dis[s]=0;   q.push(s);  inq[s]=1;
    while(!q.empty())
    {
        int u=q.front();    q.pop();    inq[u]=0;
        if(dis[s]<0)
            return 0;
        for(int i=fisrt[u];i!=-1;i=e[i].nxt)
        {
            int& v=e[i].to; int& w=e[i].w;
            if(vis[v])
                continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!inq[v])
                {
                    q.push(v);  inq[v]=1;
                }
                if(++cnt[v]>n)
                    return 0;
            }
        }
    }
    for(int i=1;i<=n;i++)
        vis[i]=vis[i]||cnt[i];
    return 1;
}

void check()
{
    for(int i=1;i<=n;i++)
        if(!vis[i])
            if(!spfa(i))
            {
                cout<<-1<<endl;
                exit(0);
            }
            else
                continue;
}

void work()
{
    memset(vis,0,sizeof(vis));
    spfa(s);
    for(int i=1;i<=n;i++)
        if(dis[i]==INF)
            cout<<"NoPath"<<endl;
        else
            out(dis[i]);
}

int main()
{
    init();
    check();
    work();
    return 0;
}

**code by PowderHan**

4

青衫白叙 LV 7 @ 2017-10-16 18:50:39

额，图连不连通怎么判？加一个超级源，将它与每个点连一条权值为0的边，跑一边spfa即可
// vijos P1053

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ins(u,v,w){e[++cnt]=(edge){v,h[u],w};h[u]=cnt;}
using namespace std;
const int N=1e3+5,M=1e5+5,inf=1e9+5;
inline int read(){
    int x=0,f=1,c=getchar();
    for(;c< '0'||c >'9';c=getchar())if(c=='-')f=-1;
    for(;c>='0'&&c<='9';c=getchar())x=x*10+c-48;
    return x*f; 
}
int n,m,s,u,v,w;
struct edge{int to,nxt,w;}e[M+N];
int h[N],cnt;
inline void lop(int &x){if(++x==N) x=1;}
int q[N],head,tail,d[N],nc[N];bool inq[N];
bool spfa(int s){
    head=tail=0;
    for(int i=1;i<=n;++i) d[i]=inf,inq[i]=nc[i]=0;
    q[tail]=s;inq[s]=nc[s]=1;lop(tail);d[s]=0;
    while(head!=tail){
        int u=q[head];inq[u]=0;lop(head);
        for(int i=h[u];i;i=e[i].nxt)
            if(d[e[i].to]>d[u]+e[i].w){
                d[e[i].to]=d[u]+e[i].w;
                if(!inq[e[i].to]){
                    inq[e[i].to]=1;q[tail]=e[i].to;lop(tail);
                    if(++nc[e[i].to]>n) return false;
                }
            }
    }
    return true;
}
int main(){
    n=read();m=read();s=read();
    for(int i=1;i<=m;++i){
        u=read();v=read();w=read();
        if(u==v&&w<0) {puts("-1");return 0;}
        if(u!=v) ins(u,v,w);
    }
    int ss=n+1;
    for(int i=1;i<=n;++i) ins(ss,i,0);
    if(!spfa(ss)) {puts("-1");return 0;}
    spfa(s);
    for(int i=1;i<=n;++i){
        if(d[i]>=inf) puts("NoPath");
        else printf("%d\n",d[i]); 
    }
    return 0;
}

JimmyChen @ 2021-02-19 23:50:51

好像确实这样比较机智

2

lrj124 LV 10 @ 2016-06-09 12:20:10

裸奔弗洛伊德
```c++
记录信息
评测状态 Time Limit Exceeded
题目 P1053 Easy sssp
递交时间 2016-06-09 12:14:34
代码语言 C++
评测机 ShadowShore
消耗时间 6481 ms
消耗内存 5408 KiB
评测时间 2016-06-09 12:14:41
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 5404 KiB, score = 0
测试数据 #1: TimeLimitExceeded, time = 1015 ms, mem = 5392 KiB, score = 0
测试数据 #2: TimeLimitExceeded, time = 1140 ms, mem = 5408 KiB, score = 0
测试数据 #3: TimeLimitExceeded, time = 1015 ms, mem = 5396 KiB, score = 0
测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 5392 KiB, score = 0
测试数据 #5: Accepted, time = 1265 ms, mem = 5408 KiB, score = 25
测试数据 #6: TimeLimitExceeded, time = 1031 ms, mem = 5396 KiB, score = 0
TimeLimitExceeded, time = 6481 ms, mem = 5408 KiB, score = 25
代码
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0xfffff,maxn = 1001;
long n,m,start,v[maxn][maxn];
bool s[maxn][maxn];
void input()
{
memset(s,false,sizeof(s));
scanf("%ld %ld %ld",&n,&m,&start);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
v[i][j] = INF;
for (int i = 1,a,b,c;i <= m;i++)
{
scanf("%d %d %d",&a,&b,&c);
v[a][b] = c;
s[a][b] = true;
}
}
#include <algorithm>
void floyd()
{
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
v[i][j] = min(v[i][j],v[i][k] + v[k][j]);
}
void work()
{
floyd();
for (int i = 1;i <= n;i++)
v[i][i] = 0;
for (int k = 1;k <= n;k++)
for (int i = 1;i <= k-1;i++)
for (int j = i+1;j <= k-1;j++)
if (s[i][j] && s[j][k] && v[k][i])
if(v[i][j]+v[j][k]+v[k][i] < 0)
{
printf("-1");
exit(0);
}
}
void output()
{
for (int i = 1;i <= n;i++)
if (v[start][i] == INF)
printf("NoPath");
else
printf("%ld\n",v[start][i]);
}
int main()
{
input();
work();
output();
return 0;
}
```

liuyiah @ 2016-08-23 16:09:11

你这裸的6
JimmyChen @ 2021-02-18 22:51:20

秀还是你秀

1

lyyyzx LV 10 @ 2016-01-30 21:48:30

本题看起来比较简单，题目也比较清楚，但是隐藏了很多陷阱，首先此题要求找负环，如果有输出-1，如果没有输出S到所有边的距离。
建图很简单，数据范围__N<=1000__,直接用矩阵存入。
但是此题的边__有重复__！，建边的时候要注意选最小的。(用邻接表存有点麻烦）
点若入队>=n次或__dist[出发点]<0__则有负环,对每个点SPFA求负环绝对超时。
所以用__Swim数组__储存经过的点，下次求负环时直接跳过标记的点。
###code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x7f7f7f
#define MAX1 1010
#define MAX2 100010

int N,M,S;

struct sssp{
//pretreatment初始化
void prepare(){
for(int i=1;i<=N;i++){
dist[i]=INF,swim[i]=false;
for(int j=1;j<=N;j++)
g[i][j]=INF;
}
}
//set map
int g[MAX1][MAX1];
inline void add(int u,int v,int val){
if(g[u][v]>val)//注意此处！数据中有重边
g[u][v]=val;
}
//
void got(int n){//建图

for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}

}
//SPFA
bool swim[MAX1];//标记已经遍历的点
bool ins[MAX1];//入队标记
int vis[MAX1];//记录入队次数
int dist[MAX1];//
queue<int> q;
bool SPFA(int s){//SPFA

for(int i=1;i<=N;i++) dist[i]=INF,vis[i]=0,ins[i]=false;
while(!q.empty()) q.pop();

q.push(s);
vis[s]++,ins[s]=true,dist[s]=0;
while(!q.empty()){
int t=q.front();q.pop();ins[t]=false;
if(dist[s]<0) return true;
for(int i=1;i<=N;i++){
if(swim[i]==true) continue;
int u=g[t][i];
if(u!=INF&&dist[i]>dist[t]+u){
dist[i]=dist[t]+u;
if(!ins[i]){
q.push(i);ins[i]=true,vis[i]++;
if(vis[i]>=N/2) return true;
}
}
}
}
for(int i=1;i<=N;i++) swim[i]=swim[i]||vis[i];
return false;
}

bool work(){
//for(int i=1;i<=N;i=i+(N/10)+1){ //随机化，减少遍历次数 i=i+(N/10)+1,但不用也可以过
for(int i=1;i<=N;i++){
if(!swim[i])
if(SPFA(i)) return true;
}
return false;
}
void work_out(){
if(work()){
printf("-1\n");
return;
}
else{
memset(swim,0,sizeof(swim));
SPFA(S);
for(int i=1;i<=N;i++){
if(dist[i]==INF) printf("NoPath\n");
else printf("%d\n",dist[i]);
}

}
}
};
sssp car={0};

int main(){
scanf("%d%d%d",&N,&M,&S);
car.prepare();
car.got(M);
car.work_out();

return 0;
}
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 4276 KiB, score = 0

测试数据 #1: Accepted, time = 0 ms, mem = 4276 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 4276 KiB, score = 15

测试数据 #3: Accepted, time = 15 ms, mem = 4272 KiB, score = 15

测试数据 #4: Accepted, time = 46 ms, mem = 4276 KiB, score = 20

测试数据 #5: Accepted, time = 46 ms, mem = 4272 KiB, score = 25

测试数据 #6: Accepted, time = 62 ms, mem = 4272 KiB, score = 15

Accepted, time = 184 ms, mem = 4276 KiB, score = 100

我也是交了N次才AP!
鉴于没有一份详尽的题解，自己写了一份。

学霸wx @ 2016-10-25 13:12:24

难道你们都没发现#0是0分吗。。。

1

SecretAgent LV 10 @ 2009-10-14 18:20:43

3行代码的程序

无语中...

begin

writeln(-1);

end.

编译通过...

├ 测试数据 01：答案错误...程序输出比正确答案长

├ 测试数据 02：答案错误...程序输出比正确答案长

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

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

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

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

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

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

Unaccepted 有效得分：75 有效耗时：0ms

0

JimmyChen LV 8 @ 2021-02-19 23:18:12

标答（大嘘）

#include <iostream>

using namespace std;

int main() {
    cout << -1 << endl;
}

这。。。这题真的就搞人心态，我倒是想看看点2的数据到底长啥样，因为INF写了个114514191（只到1e8，当然是自己傻x了）第二个点只要去掉dist[t] < 0就能过，加上就过不了，后来换成INF = 1e9，再在邻接矩阵处加了一个判定if (f[u][v] != INF)，两者应该任取其一就能过了。血的教训啊！

思路的话，基本就是优化Bellman-Ford，先判断有没有负权环，要注意可能会有不和源点连通的块，每个之前没跑过的点都访问一次就行了，上面青衫白叙的超级源点感觉更优雅方便一点，懒得改了。

判断负权环：
1. 考虑自环，在n个点的图中，任意一点最多只能和n个点有边，那理论上限就是我经过每个边都更新一次这个点，不能更多了（吗？其实很好奇会不会有更复杂，更准确地描述），所以当一个点更新数超过n(inq_cnt[u] > n)时，直接干掉。
2. 任意一次做Bellman-Ford时一旦出现源点dist[s] < 0，那也直接干掉。为什么？从源点出发，dist[s] < 0就是从一条路出去再回到源点，距离为负，那再重复一次同样的路线很明显会继续减小，必然是环，直接干掉。

Debug：
1. 如之前所述，INF不能定太小或者不判定，我只能猜要不是爆精度了，要不是别的边权绝对值都很大，导致某条INF的边加那点的dist[u]还比原来的dist[v]要小；但是问题在于既然能有这样的路径被判定成负权环，为什么(inq_cnt[] > m)的判定就不会受影响呢？理论上来说，只要有被判定成负权环，迟早也会被这种方法判断到。但是仅有这个判断的时候却过了点二，非常搞笑。
2. 前面省时间加了prev_vis[]数组，可以不用额外访问单向边指向的访问过的部分，在判定完没负权环以后还要注意memset(0)再Bellman-Ford，不然算法碰到之前标记访问过的源点直接罢工了，原地爆炸。

细节挺多，抓耳挠腮。。。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 1e3 + 145, INF = 1e9;

int n, m, s;
int f[MAXN][MAXN], dist[MAXN], inq_cnt[MAXN];
bool vis[MAXN], prev_vis[MAXN], inq[MAXN]; //Visited in this cycle; Visited in prev cycles; Nodes in queue.
queue<int> q;

int read() {
    int f = 1, x = 0;
    char ch = getchar();
    if (ch == '-') {
        f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        x *= 10;
        x += ch - '0';
        ch = getchar();
    }
    return f * x;
}

int bellmanford(int t) {
    for (int i = 0; i <= n; i++) {
        dist[i] = INF;
        vis[i] = false;
    }
    while (!q.empty()) q.pop();
    q.push(t);
    dist[t] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (inq_cnt[u] > n || dist[t] < 0) return -1;
        vis[u] = true;
        inq[u] = false;

        for (int v = 1; v <= n; v++) {
            if (prev_vis[v] || f[u][v] == INF) continue;
            if (dist[u] + f[u][v] < dist[v]) {
                dist[v] = dist[u] + f[u][v];
                if (!inq[v]) {
                    q.push(v);
                    inq_cnt[v]++;
                    inq[v] = true;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) prev_vis[i] |= vis[i];
    return 0;
}

int main() {
    n = read(); m = read(); s = read();
    
    for (int u = 1; u <= n; u++) {
        for (int v = 1; v <= n; v++) {
            f[u][v] = INF;
        }
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        u = read(); v = read(); w = read();
        f[u][v] = min(f[u][v], w);
    }

    int status_code = 0;
    for (int i = 1; i <= n; i++) {
        if (!prev_vis[i]) {
            status_code = bellmanford(i);
            if (status_code == -1) { 
                cout << -1 << endl;
                return 0;
            }
        }    
    }

    memset(prev_vis, 0, sizeof(prev_vis));
    memset(inq_cnt, 0, sizeof(inq_cnt));
    bellmanford(s);
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << "NoPath" << endl;
        } else {
            cout << dist[i] << endl;
        }
    }

    return 0;
}

0

阿里小山 LV 9 @ 2016-10-09 19:05:43

原来这么多坑。。难怪AC率如此之低。

0

dkfleet LV 10 @ 2015-06-12 09:45:46

用的如果不是Bellman-Ford,要注意此题第三个点,负权回路和源点S不连通.

0

a292695903 LV 10 @ 2015-01-27 22:04:27

spfa，点若入队》=n次则有负环，但是正常来说如果没有负环的话，不会入队几次，所以判断条件可以稍微改少点，如n/2次

0

blj2014 LV 4 @ 2014-12-24 13:27:46

评测结果
编译成功

foo.pas(16,9) Warning: Variable "lalala" does not seem to be initialized
测试数据 #0: Accepted, time = 0 ms, mem = 8696 KiB, score = 0
测试数据 #1: WrongAnswer, time = 0 ms, mem = 8692 KiB, score = 0
测试数据 #2: WrongAnswer, time = 0 ms, mem = 8692 KiB, score = 0
测试数据 #3: Accepted, time = 31 ms, mem = 8692 KiB, score = 15
测试数据 #4: Accepted, time = 187 ms, mem = 8692 KiB, score = 20
测试数据 #5: Accepted, time = 359 ms, mem = 8696 KiB, score = 25
测试数据 #6: Accepted, time = 187 ms, mem = 8692 KiB, score = 15
WrongAnswer, time = 764 ms, mem = 8696 KiB, score = 75

怎么会这样...

0

hsfzxjy LV 7 @ 2014-11-07 21:24:12

const
QN = 10000;
var
edges: array [1..1000,1..1000] of record y,w:longint;end;
en: array [1..1000] of longint;
inq: array [1..1000] of Boolean;
f,cnt: array [1..1000] of longint;
i,j,k,l,x,y,w,n,m: longint;
q: array [1..10000] of longint;
head,tail,s:longint;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);
read(n,m,s);
for i := 1 to m do
begin
read(x,y,w);
inc(en[x]);
edges[x][en[x]].y:=y;
edges[x][en[x]].w:=w;
end;
filldword(f,sizeof(f)>>2,maxlongint);
head:=0;tail:=1;q[1]:=s;inq[s]:=true;cnt[s]:=1;f[s]:=0;
while head<>tail do
begin
head:=head mod QN+1;
x:=q[head];
inq[x]:=false;
for i := 1 to en[x] do
begin
j:=edges[x][i].y;
if (f[j]>f[x]+edges[x][i].w) then
begin
inc(cnt[j]);
if cnt[j]>n then
begin
writeln(-1);
exit;
end;
f[j]:=f[x]+edges[x][i].w;
if inq[j] then continue;
inq[j] := true;
tail:=tail mod QN+1;
q[tail]:=j;
end;
end;
end;
for i := 1 to n do
if f[i]<>maxlongint then
writeln(f[i])
else
writeln('NoPath');
close(input);
close(output);
end.

为什么#2总过不去？

0

1429401938 LV 8 @ 2014-08-19 19:57:01

测试数据 #0: Accepted, time = 31 ms, mem = 72204 KiB, score = 0
测试数据 #1: Accepted, time = 62 ms, mem = 72224 KiB, score = 10
测试数据 #2: WrongAnswer, time = 109 ms, mem = 72224 KiB, score = 0
测试数据 #3: Accepted, time = 31 ms, mem = 72220 KiB, score = 15
测试数据 #4: Accepted, time = 93 ms, mem = 72216 KiB, score = 20
测试数据 #5: TimeLimitExceeded, time = 5015 ms, mem = 72224 KiB, score = 0
测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 72224 KiB, score = 0
TimeLimitExceeded, time = 6356 ms, mem = 72224 KiB, score = 45
还没-1多

0

seagull LV 8 @ 2014-06-10 17:20:49

我就把cincout改成printfscanf就过了！！！！！！天哪！！！！！
用cincout时：
测试数据 #0: Accepted, time = 31 ms, mem = 7144 KiB, score = 0
测试数据 #1: Accepted, time = 46 ms, mem = 7148 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 7148 KiB, score = 15
测试数据 #3: Accepted, time = 296 ms, mem = 7148 KiB, score = 15
测试数据 #4: TimeLimitExceeded, time = 1107 ms, mem = 7144 KiB, score = 0
测试数据 #5: Accepted, time = 1809 ms, mem = 7148 KiB, score = 25
测试数据 #6: TimeLimitExceeded, time = 1060 ms, mem = 7148 KiB, score = 0
改成printfscanf后：
测试数据 #0: Accepted, time = 0 ms, mem = 7148 KiB, score = 0
测试数据 #1: Accepted, time = 7 ms, mem = 7148 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 7144 KiB, score = 15
测试数据 #3: Accepted, time = 15 ms, mem = 7148 KiB, score = 15
测试数据 #4: Accepted, time = 109 ms, mem = 7148 KiB, score = 20
测试数据 #5: Accepted, time = 140 ms, mem = 7148 KiB, score = 25
测试数据 #6: Accepted, time = 124 ms, mem = 7144 KiB, score = 15
太可怕了！！！！！我和我的小伙伴都惊呆了！

The_Unbeatable @ 2016-11-11 20:34:41

scanf是c的输入，在cstdio
比c++输入输出流快得多

0

3300284 LV 9 @ 2014-02-25 22:57:29

我和我的小伙伴都惊呆了！我竟然不知道有负环，0分和100分的差距让我接受不了。。。

0

Tachibana LV 9 @ 2013-10-23 13:09:25

测试数据 #0: Accepted, time = 0 ms, mem = 6328 KiB, score = 0
测试数据 #1: Accepted, time = 15 ms, mem = 6332 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 6328 KiB, score = 15
测试数据 #3: Accepted, time = 140 ms, mem = 6328 KiB, score = 15
测试数据 #4: Accepted, time = 968 ms, mem = 6328 KiB, score = 20
测试数据 #5: Accepted, time = 406 ms, mem = 6328 KiB, score = 25
测试数据 #6: Accepted, time = 62 ms, mem = 6332 KiB, score = 15
Accepted, time = 1606 ms, mem = 6332 KiB, score = 100
第四个点= = .... 吓死爹了。

WJCwjc142857 @ 2017-09-28 06:39:13

卡常大法好

0

SEX丶Elope LV 6 @ 2013-02-16 10:17:22

点击查看程序源码+详细题解

0

Rabxian LV 7 @ 2012-10-26 21:54:27

├ 测试数据 01：答案正确... (0ms, 12492KB)

├ 测试数据 02：答案正确... (0ms, 12492KB)

├ 测试数据 03：答案正确... (0ms, 12492KB)

├ 测试数据 04：答案正确... (0ms, 12492KB)

├ 测试数据 05：答案正确... (0ms, 12492KB)

├ 测试数据 06：答案正确... (0ms, 12492KB)

├ 测试数据 07：答案正确... (0ms, 12492KB)

终于ac了。。。这套题各种第七个点wa。。。我也不知道为什么，把整道题重新写了一遍居然就ac了，真是神奇。

这道题判断负环我用的是dist，如果有负环那么这个负环一定和start相连。

choversky @ 2015-09-01 14:40:59

第七个到底是为什么啊。。

0

pilipala195 LV 8 @ 2012-10-15 20:12:42

├ 测试数据 01：答案正确... (0ms, 24264KB)

├ 测试数据 02：答案正确... (0ms, 24264KB)

├ 测试数据 03：答案正确... (0ms, 24264KB)

├ 测试数据 04：答案正确... (0ms, 24264KB)

├ 测试数据 05：答案正确... (0ms, 24264KB)

├ 测试数据 06：答案正确... (0ms, 24264KB)

├ 测试数据 07：答案正确... (0ms, 24264KB)

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|

好吧，用的空间大了些。。。。

还有一个比较猥琐的办法判断负环，当spfa的栈接近于爆时，便有负环。。。空间就开大点吧，两次spfa，一次对于随机的一个点判断负环，一次对于s做，AC。

顺求各位大神笼罩，保我noip。ORZ

0

c16jjh LV 9 @ 2012-09-06 09:54:03

我终于知道这道题为啥这么低Ac率了..

是因为有这么一群英雄好汉勇于向P1053发起攻击,倒了然后站起来继续攻打~~

有的人胜利了,就在这里发题解,引人传唱,永垂不朽

有的人遍体鳞伤后决定放弃,于是在这里留下名字作为纪念

更有的人还踌躇满志地誓要搞掂这道题,~!!!!

0

xwh9315 LV 8 @ 2012-08-09 15:44:53

spfa+判断、、

交了4次。。

陷阱确实多，

1.s不一定在负权回路里，所以如果直接对s做spfa，会错。

2.两点之间居然有可能有多条边。。。读数据的时候，不要一味的覆盖，要保留两点之间最小值的边。

我的做法就是对每个点都进行spfa，这样判断负环回路大家都会的，看入队次数是否大于n。但是单纯这样会tle，所以做如下优化（ps：我没做到0ms，但是，可以过了，希望大牛帮忙继续优化）

优化

1.在枚举每个顶点进行SPFA时，可以判断某个顶点之前枚举时是否入过队列，如果有入过的话，则代表这个顶点有无负权回路已经被计算过，可以不再计算。

2.在枚举的过程中，当这个顶点的最短路(d)

题解

129 条题解

状态耗时内存占用

Easy sssp

信息

状态

开发

支持

题解

129 条题解

状态 耗时 内存占用

Easy sssp

信息

状态

开发

支持

还没有账户？

登录

状态耗时内存占用