题解

128 条题解

  • 6
    @ 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**
    
  • 1
    @ 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;
    }
    
    
  • 1
    @ 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;
    }
    ```

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

      你这裸的6

  • 1
    @ 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!
    鉴于没有一份详尽的题解,自己写了一份。

    • @ 2016-10-25 13:12:24

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

  • 0
    @ 2016-10-09 19:05:43

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

  • 0
    @ 2015-06-12 09:45:46

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

  • 0
    @ 2015-01-27 22:04:27

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    太可怕了!!!!!我和我的小伙伴都惊呆了!

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

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

  • 0
    @ 2014-02-25 22:57:29

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

  • 0
    @ 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
    第四个点= = .... 吓死爹了。

  • 0
    @ 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相连。

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

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

  • 0
    @ 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
    @ 2012-09-06 09:54:03

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

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

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

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

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

  • 0
    @ 2012-08-09 15:44:53

    spfa+判断、、

    交了4次。。

    陷阱确实多,

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

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

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

    优化

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

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

  • 0
    @ 2012-07-18 15:00:46

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

  • 0
    @ 2010-03-14 15:55:56

    提交了26遍

    甚至照标程改了n遍

    但始终没A

    最后的教训是

    c++一定要用scanf和printf

    不能用cin和cout!!!

信息

ID
1053
难度
8
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
6945
已通过
594
通过率
9%
上传者