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 6 @ 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

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

Szx2012 LV 10 @ 2012-07-18 15:00:46

囧编译通过... ├ 测试数据 01：答案正确... 0ms ├ 测试数据 02：答案正确... 0ms ├ 测试数据 03：答案错误...程序输出比正确答案长 ├ 测试数据 04：答案正确... 0ms ├ 测试数据 05：答案正确... 0ms ├ 测试数据 06：答案错误...程序输出比正确答案长 ├ 测试数据 07：答案错误...　├ 标准行输出　├ 错误行输出 ------------------------- Unaccepted 有效得分：45 有效耗时：0ms

0

哈凌大侠 LV 5 @ 2010-03-14 15:55:56

提交了26遍

甚至照标程改了n遍

但始终没A

最后的教训是

c++一定要用scanf和printf

不能用cin和cout！！！

954899524 @ 2013-03-31 21:31:03

cin,cout tooslow

0

sliverzero LV 8 @ 2010-03-09 18:40:57

郁闷啊。。。第七个数据怎么回事会比正解小...我连两点多路都处理了啊。。。

0

mintalfance LV 10 @ 2009-11-09 14:29:17

编译通过...

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

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

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

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

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

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

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

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

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

A了！虽然不是巨快如闪电

就是先对s用spfa，如果没有出现负权环就对与s不连通的点spfa

纠结啊，还是过了。。

0

chen199277 LV 10 @ 2009-11-09 13:32:03

感觉dfs n*n 不能判断负环啊。

应该是cheat吧。

对每个连同块。spfa才是王道

0

zhujf553 LV 10 @ 2009-11-04 08:09:46

编译通过...

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

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

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

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

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

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

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

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

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

判断环有个很好的优化

while(op < cl)

{

k = q[op];

v[k] = true;

for(j = e[k] ; j != -1 ; j = edge[j].next)

{

i = edge[j].t;

if(d[k] + edge[j].v < d[i])

{

d[i] = d[k] + edge[j].v;

if(!inq[i])

{

inq[i] = true;

q[cl] = i;

cl++;

co[i]++;

if(co[i] >= n - 1)return -1;

}

}

}

inq[k] = false;

op++;

if(d < 0) //在这里是一个环的优化

{

return -1;

}

}

0

吴越 LV 9 @ 2009-11-02 23:20:16

经过无数次提交wa的惨痛教训，第2组显示标准输出比选手输出长的同学注意判断负环的时候要写>n 不能写 >=n 啊！！！

0

darin LV 10 @ 2009-11-02 22:35:01

lx正解，，此题最ws的地方就是和s不连的负环。。哎，，阴险啊。。是说这通过率....

0

src250 LV 10 @ 2009-10-29 22:09:01

编译通过...

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

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

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

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

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

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

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

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

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

数据弱，每个联通块只要SPFA一下找负权环就行了。没出那种用每个联通块的第一个点做SPFA会出错的数据。比如

4 4 1

1 2 5

2 3 -1

3 4 -1

4 2 -1

我们用1做SPFA，显然没办法找到负权环2 3 4。

所以深搜找负权环比较好。但是我太菜了，以至于老超时，于是用上述方法cheat了。实在囧啊！

0

雨中的风筝 LV 10 @ 2009-10-24 10:14:34

35次提交后得到的教训。。。要用int64，初值要大一些

0

艾弗森 LV 8 @ 2009-10-06 21:17:02

为啥你们能秒杀。。

0

zxytim LV 10 @ 2009-10-06 19:58:41

1.居然有不和S在一个连通块里面的负环。。。。。

2.不看题解不知道。。。读进来的可能有重边。。要取最小的那个。。orz

后来者注意。。

0

xiedong1993 LV 8 @ 2009-10-03 09:10:28

这个题好猥琐~~~

题解

129 条题解

状态耗时内存占用

Easy sssp

信息

状态

开发

支持

题解

129 条题解

状态 耗时 内存占用

Easy sssp

信息

状态

开发

支持

还没有账户？

登录

状态耗时内存占用