95 条题解

  • 2
    @ 2017-08-11 11:08:30

    /*
    我用的是Dijkstra算法。。。
    采用贪心策略,每次新扩展一个RP最大的点,再以这个点为中间点,更新其他所有点的最大RP。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。
    对于有n个房间的图,求图中房间1到其他所有顶点的最短路径时,可分以下几个步骤来设计:
    把图的所有房间分成两组,一组为已经计算好最大RP的顶点,设为A组,另一组为还未计算的房间,设为B组。初始时所有顶点放在B组,而先将顶点1放入A组。
    从B组中找出从房间1能到达最大RP的房间vj(1<=j<=n),
    将vj加入A组,同时以vj为中间点,更新vi到B组中所有房间的最大RP。
    重复上一步,直至B组中所有点加入到A组中。
    算法实现:用一个一维数组flag记录顶点在哪个组。当flag[i]为1时,i顶点在A组,flag[i]为0时,i顶点在B组。用dis[i][j]记录房间i至j的最大RP,初始时,有边相连的两个房间dis[i][j]的值为边权,无边相连的dist[i][j]值为0。
    */
    #include<iostream>
    using namespace std;
    long long dis[2001][2001]={0};
    long long flag[2001]={0};
    long long n,m,i,j,k,l;
    int main()
    {
    flag[1]=1;
    cin>>n;
    while(true)
    {
    cin>>i>>j>>k;
    if(i==0&&j==0&&k==0)
    {
    break;
    }
    dis[i][j]=k;
    }
    for(i=2;i<=n;i++)
    {
    m=-9999999;
    for(j=1;j<=n;j++)
    {
    if(!flag[j]&&dis[1][j]>m)
    {
    k=j;
    m=dis[1][j];
    }
    }
    flag[k]=1;
    for(j=1;j<=n;j++)
    {
    if(!flag[j])
    {
    dis[1][j]=max(dis[1][j],min(dis[1][k],dis[k][j]));
    }
    }
    }
    for(i=2;i<=n;i++)
    {
    cout<<dis[1][i]<<endl;
    }
    return 0;
    }

  • 1
    @ 2019-07-26 16:30:45

    第一想法就是floyd,虽然时间复杂度不好看,但是代码简单。
    果然时间复杂度的原因,floyd只过了前三个点。

    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int tube[2001][2001];
    int n;
    
    int main()
    {
        memset(tube,0,sizeof(tube));
        int i,j,k;
        cin>>n;
        while(true)
        {
            cin>>i>>j>>k;
            if(i==0&&j==0&&k==0)
            {
                break;
            }
            else
            {
                tube[i][j]=k;
            }
        }
        int mi;
        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    mi=min(tube[i][k],tube[k][j]);
                    if(tube[i][j]<mi)
                    {
                        tube[i][j]=mi;
                    }
                }
            }
        }
        for(i=2;i<=n;i++)
        {
            cout<<tube[1][i]<<endl;
        }
        return 0;
    }
    

    之后改用Dijkstra,过了。

    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int tube[2001][2001];
    int n;
    bool vis[2001]={0};
    int ans[2001]={0};
    int lacc=0,acc=0;
    
    int main()
    {
        memset(tube,0,sizeof(tube));
        int i,j,k;
        cin>>n;
        while(true)
        {
            cin>>i>>j>>k;
            if(i==0&&j==0&&k==0)
            {
                break;
            }
            else
            {
                tube[i][j]=k;
            }
        }
        int mi,index;
        /*
        //floyd
        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    mi=min(tube[i][k],tube[k][j]);
                    if(tube[i][j]<mi)
                    {
                        tube[i][j]=mi;
                    }
                }
            }
        }
        */
        //dij
        ans[1]=1e9;
        while(true)
        {
            mi=0;
            for(i=1;i<=n;i++)
            {
                if(!vis[i]&&ans[i]>mi)
                {
                    mi=ans[i];
                    index=i;
                }
            }
            if(mi>0)
            {
                acc++;
                vis[index]=true;
                for(i=1;i<=n;i++)
                {
                    if(!vis[i])
                    {
                        ans[i]=max(ans[i],min(ans[index],tube[index][i]));
                    }
                }
            }
            if(lacc==acc)
            {
                break;
            }
            else
            {
                lacc=acc;
            }
        }
        for(i=2;i<=n;i++)
        {
            cout<<ans[i]<<endl;
        }
        return 0;
    }
    
  • 0
    @ 2017-06-02 23:38:24

    Dijsktra堆优化
    c++
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    #define oo 0x3f3f3f
    using namespace std;
    const int N = 2005 ;
    int n,a,b,r,tot = 0;
    struct Edge{
    int u,v,w,next;
    }e[N<<2];
    struct node{
    int u,ans;
    bool operator < (const node &A) const{
    return ans<A.ans;
    }
    };
    int head[N],vis[N],d[N];
    inline void adde(int u,int v,int w){
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot;
    }
    inline void Dijsktra(int s){
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));d[s]=oo;
    priority_queue <node> q;
    q.push((node){s,d[s]});
    while(!q.empty()){
    node now=q.top();q.pop();
    if(vis[now.u]) continue ;
    vis[now.u]=1;
    for(int i=head[now.u];i!=-1;i=e[i].next){
    int v=e[i].v;
    if(d[v]<min(now.ans,e[i].w)){
    d[v]=min(now.ans,e[i].w);
    q.push((node){v,d[v]});
    }
    }
    }
    }
    int main(){
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    while(scanf("%d%d%d",&a,&b,&r)==3 && a!=0) adde(a,b,r);
    Dijsktra(1);
    for(int i=2;i<=n;i++) printf("%d\n",d[i]);
    return 0;
    }

  • 0
    @ 2017-02-20 20:54:47

    Dijkstra
    var
    dist:array[1..2000, 1..2000] of longint;
    flag:array[1..2000] of boolean;
    n, i, j, pos, max:longint;
    function min(a, b:longint):longint;
    begin
    if a<b then exit(a)
    else exit(b)
    end;
    begin
    readln(n);
    readln(i, j, pos);
    fillchar(dist, sizeof(dist), 0);
    while (i<>0) and (j<>0) and (pos<>0) do begin
    dist[i, j]:=pos;
    readln(i, j, pos)
    end;
    fillchar(flag, sizeof(flag), 0);
    flag[1]:=true;
    for i:=2 to n do begin
    max:=0;
    for j:=1 to n do if (not(flag[j])) and (dist[1, j]>max) then begin
    pos:=j;
    max:=dist[1, j]
    end;
    flag[pos]:=true;
    for j:=1 to n do if (not(flag[j])) and (min(dist[1, pos], dist[pos, j])>dist[1, j]) then dist[1, j]:=min(dist[1, pos], dist[pos, j])
    end;
    for j:=2 to n do writeln(dist[1, j])
    end.

  • 0
    @ 2016-11-17 16:41:59

    spfa
    #include <cstdio>
    #include <queue>
    #include <algorithm>
    #define O 2100
    using std::min;
    struct edge{
    int v,val;
    edge *link;
    };

    int n,top=0;
    edge graph[O]={0};
    edge node[O*O];

    void add(int u,int v,int val){
    edge *l=&node[top++];
    l->v=v,l->val=val;
    l->link=graph[u].link;
    graph[u].link=l;
    }

    void build(){
    scanf("%d",&n);
    int u,v,val;
    do{
    scanf("%d%d%d",&u,&v,&val);
    add(u,v,val);
    }while(u&&v&&val);
    }

    //SPFA
    std::queue<int> q;
    int inque[O]={0};
    int dist[O];

    void spfa(int u){
    for(int i=2;i<=n;i++)
    dist[i]=0;
    dist[1]=99999999;
    q.push(u),inque[u]=1;
    while(!q.empty()){
    int t=q.front();
    q.pop(),inque[t]=0;
    edge *l=graph[t].link;
    while(l){
    int z=min(l->val,dist[t]);
    if(dist[l->v]<z){
    dist[l->v]=z;
    if(!inque[l->v]){
    q.push(l->v);
    inque[l->v]=1;
    }

    }

    l=l->link;
    }
    }
    }

    int main(){
    freopen("in.txt","r",stdin);
    build();
    spfa(1);
    for(int i=2;i<=n;i++)
    printf("%d\n",dist[i]);

    return 0;
    }

  • 0
    @ 2016-11-15 20:05:10

    普通spfa

    #include<queue>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int head[2005],dis[2005],tov[2000005],nex[2000005];
    int w[2000005],tot,judge[2005];
    inline void add(int a,int b,int c)
    {
    tov[++tot]=b;
    nex[tot]=head[a];
    head[a]=tot;
    w[tot]=c;
    }
    inline void spfa()
    {
    queue<int>q;
    q.push(1);dis[1]=0x7f7f7f7f;
    while(!q.empty())
    {
    int k=q.front();q.pop();
    int t=head[k];judge[k]=0;
    while(tov[t])
    {
    if(dis[tov[t]]<min(dis[k],w[t]))
    {
    dis[tov[t]]=min(dis[k],w[t]);
    if(!judge[tov[t]])
    {
    q.push(tov[t]);
    judge[tov[t]]=1;
    }
    }
    t=nex[t];
    }
    }
    }
    int main()
    {
    int n;scanf("%d",&n);
    while(1)
    {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a==0)break;
    add(a,b,c);
    }
    spfa();
    for(int i=2;i<=n;i++)
    printf("%d\n",dis[i]);
    }

  • 0
    @ 2016-10-19 18:09:21
    minx=min(l->val,dist[t]);
    if(dist[l->dest]<minx)
    dist[l->dest]=minx;
    

    dist[1]不能为0。

  • 0
    @ 2016-10-17 18:41:54

    #include <cstdio>
    #include <cstring>
    #include <queue>
    #define INF -1000000
    using std::queue;

    struct edge{
    int d,v;
    struct edge *link;
    };

    int top=1,n,m;
    edge graph[2001]={0};
    edge node[4000001];

    void read(int s,int d,int v){
    edge *l;
    l=&node[top];
    l->d=d;
    l->v=v;
    l->link=graph[s].link;
    graph[s].link=l;
    top++;
    }

    void build(){
    scanf("%d",&n);
    int s,d,v;
    do{
    scanf("%d%d%d",&s,&d,&v);
    read(s,d,v);
    }while(s);
    }

    //SPFA

    int inque[2001]={0};
    int dist[2001];
    queue <int> q;

    void spfa(int s){
    for(int i=1;i<=n;i++)
    dist[i]=0;
    q.push(s);
    inque[s]=1;
    dist[s]=0;
    edge *l;
    int t;
    int minthis;
    int chg=0;
    while(!q.empty()){
    t=q.front();
    q.pop();
    inque[t]=0;
    l=graph[t].link;
    while(l){
    minthis=dist[t]<l->v?dist[t]:l->v;
    if(l->d>0&&minthis>dist[l->d]||!dist[t]){
    if(!dist[t])
    dist[l->d]=l->v;
    else
    dist[l->d]=minthis;
    if(inque[l->d]==0){
    q.push(l->d);
    inque[l->d]=0;
    }
    }
    l=l->link;
    }
    }
    }

    int main(){
    build();
    spfa(1);
    for(int i=2;i<=n;i++)
    printf("%d\n",dist[i]);
    return 0;
    }

  • 0
    @ 2016-08-26 07:44:29

    测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 628 KiB, score = 10
    测试数据 #3: Accepted, time = 46 ms, mem = 820 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 820 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 820 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 820 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 824 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 820 KiB, score = 10
    测试数据 #9: Accepted, time = 31 ms, mem = 820 KiB, score = 10
    Accepted, time = 231 ms, mem = 824 KiB, score = 100
    代码
    #include"iostream"
    #include"stdio.h"
    #include"vector"
    #include"functional"
    #include"string"
    #include"cstring"
    #include"algorithm"
    #include"queue"
    using namespace std;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    const int maxn=2000+20;
    const int INF=100000000;
    struct edge
    {
    int from,to,dist;
    edge(int u,int v,int w){from=u;to=v;dist=w;}
    edge(){}
    };
    struct dijkstra
    {
    int n,m;
    vector<int>g[maxn];
    vector<edge>edges;
    int visit[maxn];
    int pre[maxn];
    int road[maxn];
    int d[maxn];
    void get_path(int s,int e,vector<int>& path){
    int pos = e;
    while(1){
    path.push_back(pos+1);
    if(pos == s)
    break;
    pos = pre[pos];
    }
    }
    void init(int n){this->n=n;for(int i=0;i<n;i++)g[i].clear();edges.clear();}
    void add_edge(int u,int v,int w){edges.push_back(edge(u,v,w));int m=edges.size();g[u].push_back(m-1);}
    void djk(int s)
    {
    queue<pii>Q;
    memset(visit,0,sizeof(visit));
    for(int i=0;i<n;i++) d[i]=0;
    d[s]=INF;
    Q.push(make_pair(d[s],s));
    visit[s]=1;
    while(!Q.empty())
    {
    pii x=Q.front();Q.pop();
    int u=x.second;
    visit[u]=0;
    for(int i=0;i<g[u].size();i++)
    {
    edge& e=edges[g[u][i]];
    if(d[e.to]<min(e.dist,d[e.from]))
    {
    d[e.to]=min(e.dist,d[e.from]);
    if(!visit[e.to])
    {
    Q.push(make_pair(d[e.to],e.to));
    visit[e.to]=1;
    }

    }

    }
    }

    }
    };
    int main()
    {
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    int n;
    int first=1;
    while(scanf("%d",&n)==1)
    {
    int u,v,w;
    dijkstra a;
    a.init(n);
    while(scanf("%d%d%d",&u,&v,&w)==3&&(u+v+w))
    {
    u--;v--;
    a.add_edge(u,v,w);
    }
    a.djk(0);
    for(int i=1;i<n;i++)
    cout<<a.d[i]<<endl;
    }
    return 0;
    }

  • 0
    @ 2016-08-26 07:41:48

    /
    乌龟速度跑完了。
    我的思路是
    每次更新都是选择 d[j]=max(d[j],min(w[i,j],d[i]))
    */

    #include"iostream"
    #include"stdio.h"
    #include"vector"
    #include"functional"
    #include"string"
    #include"cstring"
    #include"algorithm"
    #include"queue"
    using namespace std;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    const int maxn=2000+20;
    const int INF=100000000;
    struct edge
    {
    int from,to,dist;
    edge(int u,int v,int w){from=u;to=v;dist=w;}
    edge(){}
    };
    struct dijkstra
    {
    int n,m;
    vector<int>g[maxn];
    vector<edge>edges;
    int visit[maxn];
    int pre[maxn];
    int road[maxn];
    int d[maxn];
    void get_path(int s,int e,vector<int>& path){
    int pos = e;
    while(1){
    path.push_back(pos+1);
    if(pos == s)
    break;
    pos = pre[pos];
    }
    }
    void init(int n){this->n=n;for(int i=0;i<n;i++)g[i].clear();edges.clear();}
    void add_edge(int u,int v,int w){edges.push_back(edge(u,v,w));int m=edges.size();g[u].push_back(m-1);}
    void djk(int s)
    {
    priority_queue<pii,vector<pii>,greater<pii> >Q;
    memset(visit,0,sizeof(visit));
    for(int i=0;i<n;i++) d[i]=0;
    d[s]=INF;
    Q.push(make_pair(d[s],s));
    visit[s]=1;
    while(!Q.empty())
    {
    pii x=Q.top();Q.pop();
    int u=x.second;
    visit[u]=0;
    //cout<<"u:"<<u<<endl;
    for(int i=0;i<g[u].size();i++)
    {
    edge& e=edges[g[u][i]];
    if(d[e.to]<min(e.dist,d[e.from]))
    {
    d[e.to]=min(e.dist,d[e.from]);
    //cout<<"e.to="<<e.to<<" "<<"e.dist="<<e.dist<<" "<<"d[e.from]="<<d[e.from]<<endl;
    if(!visit[e.to])
    {
    Q.push(make_pair(d[e.to],e.to));
    visit[e.to]=1;
    }

    }

    }
    //cout<<endl;
    }

    }
    };
    int main()
    {
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    int n;
    int first=1;
    while(scanf("%d",&n)==1)
    {
    int u,v,w;
    dijkstra a;
    a.init(n);
    while(scanf("%d%d%d",&u,&v,&w)==3&&(u+v+w))
    {
    u--;v--;
    a.add_edge(u,v,w);
    }
    a.djk(0);
    for(int i=1;i<n;i++)
    cout<<a.d[i]<<endl;
    }
    return 0;
    }

  • 0
    @ 2016-08-11 14:13:50

    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:42:7: warning: 'num' may be used uninitialized in this function [-Wmaybe-uninitialized]
    int num;
    ^
    测试数据 #0: Accepted, time = 15 ms, mem = 16260 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 16260 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 16260 KiB, score = 10
    测试数据 #3: Accepted, time = 78 ms, mem = 16260 KiB, score = 10
    测试数据 #4: Accepted, time = 62 ms, mem = 16264 KiB, score = 10
    测试数据 #5: Accepted, time = 62 ms, mem = 16264 KiB, score = 10
    测试数据 #6: Accepted, time = 62 ms, mem = 16260 KiB, score = 10
    测试数据 #7: Accepted, time = 62 ms, mem = 16260 KiB, score = 10
    测试数据 #8: Accepted, time = 93 ms, mem = 16260 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 16260 KiB, score = 10
    Accepted, time = 557 ms, mem = 16264 KiB, score = 100

    orz
    /*
    各种大犇都是用的SPFA算法撸了两遍,窝就是这么6用Dijkstra算法做23333
    Dijkstra算法变形,注意如何找当前需要的用来更新值的下家,并且如何更新;
    初始化问题一定要注意,此题数据弱,若数据过大,
    则应该用堆或者优先队列优化的Dijkstra算法来做
    但是事实告诉我们这是一道水题23333orz
    然而差点不能一遍过,还好多对拍了一会
    此题亮点:
    Dijkstra变形QWQ
    只会做水题的Powder
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;

    const int INF=0x7fffff;//QAQ好像这个INF并无任何很大卵用
    int d[2002];
    int v[2002];//标记是否到过
    int a[2002][2002];
    int n;

    int main()
    {
    cin>>n;
    int x,y,w;
    memset(a,0,sizeof(a));//a初始化应为0,即无法到达
    while(cin>>x>>y>>w)
    {
    if(x==0&&y==0&&w==0)
    break;
    a[x][y]=w;
    }
    int s=1;
    v[1]=1;
    for(int i=2;i<=n;i++)
    d[i]=a[s][i];
    for(int i=1;i<=n;i++)
    {
    int MAX=0;
    int num;
    for(int j=1;j<=n;j++)//每次找到所有未访问点中距离最大的值
    if(!v[j]) //类似于最短路中最短边
    {
    if(d[j]>MAX)
    MAX=d[j],num=j;//更新并记录此值
    }
    v[num]=1;//加入集合中
    for(int j=1;j<=n;j++)//用此最大rp值去更新各个点的rp值
    if(!v[j])
    if(d[j]<min(d[num],a[num][j]))//必须要比d[num]小且比a[num][j]小才行
    d[j]=min(d[num],a[num][j]);//类似于d[num]+a[num][j]但是要注意只要取最小值就好惹
    }
    for(int i=2;i<=n;i++)
    cout<<d[i]<<endl;
    return 0;
    }

  • 0
    @ 2016-06-22 21:01:55

    没什么好说的,就是一定记得到不了输出0……不要问我怎么知道的……爆0的原因之一……
    ```c++
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int INF = 2147483647;
    const int maxn = 2100;

    struct Ed
    {
    int from,to,limit;
    Ed(int a=0,int b=0,int c=0) : from(a),to(b),limit(c){}
    };

    int n,limit_min[maxn];
    bool inq[maxn];
    vector<Ed> edges;
    vector<int> G[maxn];
    queue<int> q;

    void SPFA()
    {
    memset(limit_min,0,sizeof(limit_min));
    memset(inq,0,sizeof(inq));
    q.push(1);inq[1]=true;
    limit_min[1]=INF;

    while(!q.empty())
    {
    int now=q.front();q.pop();
    inq[now]=false;
    for(int i=0;i<(int)G[now].size();i++)
    {
    Ed &e=edges[G[now][i]];
    int k=min(limit_min[now],e.limit);
    if(k>limit_min[e.to])
    {
    limit_min[e.to]=k;
    if(!inq[e.to]) { q.push(e.to);inq[e.to]=true; }
    }
    }
    }
    }

    int main()
    {
    scanf("%d",&n);
    while(true)
    {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a==0&&b==0&&c==0) break;
    edges.push_back(Ed(a,b,c));
    G[a].push_back(edges.size()-1);
    }

    SPFA();
    for(int i=2;i<=n;i++)
    printf("%d\n",limit_min[i]);
    return 0;
    }

    /* Accepted, time = 231 ms, mem = 796 KiB, score = 100 2016年6月22日星期三 */
    ```

  • 0
    @ 2016-02-14 00:13:35

    这道题太水了。。。
    Dijkstra用二叉堆优化后0ms过!!!
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 47588 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 47584 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 47584 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 47588 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 47584 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 47584 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 47584 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 47588 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 47584 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 47588 KiB, score = 10
    Accepted, time = 0 ms, mem = 47588 KiB, score = 100
    我也是醉了。。。

  • 0
    @ 2016-02-01 18:25:21

    好久没一遍A了..
    评测结果
    编译成功

    foo.cpp: In function 'void spfa(int)':
    foo.cpp:52:27: warning: statement has no effect [-Wunused-value]
    flag[u];
    ^
    测试数据 #0: Accepted, time = 0 ms, mem = 1108 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1108 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1108 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1108 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1108 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 1108 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 1112 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 1108 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 1112 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 1108 KiB, score = 10
    Accepted, time = 45 ms, mem = 1112 KiB, score = 100
    代码
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <cstdlib>
    #include <time.h>
    #define N 20000
    #define INF 1<<29
    using namespace std;

    int n;
    int p[N],flag[N],dis[N];

    struct node
    {
    int a,b,w,nt;
    }e[N];

    int nn;
    void anode(int x,int y,int z)
    {
    nn++;
    e[nn].a=x;
    e[nn].b=y;
    e[nn].w=z;
    e[nn].nt=p[x];
    p[x]=nn;
    }

    void spfa(int x)
    {
    flag[x]=1;
    queue<int>q;
    q.push(x);
    dis[x]=INF;
    while(!q.empty())
    {
    int k=q.front();
    q.pop();
    flag[x]=0;
    for(int i=p[k];i;i=e[i].nt)
    {
    int neww=min(dis[k],e[i].w);
    int u=e[i].b;
    if(dis[u]<neww)
    {
    dis[u]=neww;
    if(!flag[u])
    {
    flag[u];
    q.push(u);
    }
    }
    }
    }
    }

    int main()
    {
    //freopen("D:\test\in.txt","r",stdin);
    scanf("%d",&n);
    int x,y,z;
    while(scanf("%d%d%d",&x,&y,&z),x!=0||y!=0||z!=0) anode(x,y,z);
    memset(dis,-1,sizeof(dis));
    spfa(1);
    for(int i=2;i<=n;i++)
    {
    if(dis[i]!=-1) printf("%d\n",dis[i]);
    else printf("0\n");
    }
    return 0;
    }

  • 0
    @ 2015-11-04 16:08:38

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 3228 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 3228 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 3228 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 3228 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 3228 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 3228 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 3228 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 3224 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 3228 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 3224 KiB, score = 10
    Accepted, time = 45 ms, mem = 3228 KiB, score = 100

    数组开太大也会WA。。。醉了。。。

  • 0
    @ 2015-10-25 00:06:35

    //
    // main.cpp
    // a
    //
    // Created by alldream on 15-10-24.
    // Copyright (c) 2015骞?jzy. All rights reserved.
    //

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

    const int maxn = 1005;
    const int maxm = 1000055;
    const int inf = 0x3fffffff;

    struct Edge{
    int f,t,we;
    int next;
    }E[maxm];

    int c,pre[maxn];

    void clear(){
    c = 0;
    memset(pre,-1, sizeof(pre));
    }

    void insert(int f,int t,int we){
    E[c].f=f;E[c].t=t;E[c].we=we;E[c].next=pre[f];pre[f]=c++;
    }

    int maxa(int a,int b){
    if(a >=b) return a;
    return b;
    }

    int main(int argc, const char * argv[]) {
    int n;
    cin>>n;
    int dist[n+1];
    memset(dist,0, sizeof(dist));
    bool isOK[n+1];
    memset(isOK,0, sizeof(isOK));
    int f,t,we;
    cout<<n;
    while (scanf("%d%d%d",&f,&t,&we) ==3) {
    cout<<f<<t<<we;
    if(f == 0) break;
    insert(f, t, we);
    insert(t, f, we);
    }
    dist[1]=inf;
    int v = 1;
    int max = inf;
    for (int j = 1; j < n; ++j) {
    for (int i = pre[v]; i != -1; i = E[i].next) {
    int t = E[i].t;
    int we = E[i].we;
    dist[t] = maxa(dist[t],min(dist[f],we));
    }
    isOK[v]=1;
    for(int i = 0;i < n;++i){
    if(!isOK[i]){
    if (max > dist[i]) {
    max = dist[i];
    v = i;
    }
    }
    }
    }
    cout<<&dist[1]<<endl;

    return 0;
    }

  • 0
    @ 2015-03-26 21:33:37

    SPFA....到不了一定记得打0....QAQ....
    #include <stdio.h>
    #include <iostream>
    #include <queue>
    using namespace std;
    int adj[2001],nex[10001],head[10001],wei[10001],tot;
    void add();
    void add(int u,int v,int w){
    tot++;
    adj[tot]=v;
    wei[tot]=w;
    nex[tot]=head[u];
    head[u]=tot;
    return ;
    }
    int main (){
    int i,n,x,y,z,k,dis[2001];
    bool inqueue[2001];
    queue <int>q;
    freopen ("escape.in","r",stdin);
    freopen ("escape.out","w",stdout);
    scanf ("%d",&n);
    while (scanf ("%d%d%d",&x,&y,&z),x!=0||y!=0||z!=0){
    add(x,y,z);
    }
    memset (dis,-1,sizeof (dis));
    memset (inqueue,false,sizeof (inqueue));
    q.push (1);
    dis[1]=2147483647;
    while (!q.empty ()){
    k=q.front ();
    q.pop();
    inqueue[k]=false;
    for (i=head[k];i!=0;i=nex[i]){
    int we=min (dis[k],wei[i]);
    if (dis[adj[i]]<we){
    dis[adj[i]]=we;
    if (!inqueue[adj[i]]){
    q.push (adj[i]);
    inqueue[adj[i]]=true;
    }
    }
    }
    }
    for (i=2;i<=n;i++){
    if (dis[i]==-1)
    printf ("0\n");
    else
    printf ("%d\n",dis[i]);
    }
    return 0;
    }

  • 0
    @ 2015-03-20 20:38:52

    不知道这算不算dijsktra
    基本思路就是保存 Max { Min { 起点->源点, 源点-> 终点 } } (依次枚举终点)

    #include <stdio.h>
    #include <limits.h>
    #define MIN(a,b) ((a)<(b)?(a):(b))
    int map[2000][2000];
    int dijkstra[2000];
    int searched[2000];
    int main(){
    int num,distance;
    int i,k,source,max,index;
    scanf("%d",&num);
    for(i=0;i<num;i++){
    for(k=0;k<num;k++)
    map[i][k]=0;
    searched[i]=0;
    dijkstra[i]=0;
    }
    while(1){
    scanf("%d%d%d",&i,&k,&distance);
    if(i==0 || k==0 || distance==0)
    break;
    map[i-1][k-1]=distance;
    }
    dijkstra[0]=LONG_MAX;
    source=0;
    for(i=0;i<num;i++){
    searched[source]=1;
    max=0;
    for(k=0;k<num;k++){
    if(!searched[k]){
    if(map[source][k]>0){
    if(MIN(dijkstra[source],map[source][k])>dijkstra[k])
    dijkstra[k]=MIN(dijkstra[source],map[source][k]);
    }
    if(dijkstra[k]>max){
    max=dijkstra[k];
    index=k;
    }
    }
    }
    source=index;
    }
    for(i=1;i<num;i++)
    printf("%d\n",dijkstra[i]);
    return 0;
    }

    • @ 2015-03-22 20:09:25

      肯定是抄了1635的代码。。。还index。。。

  • 0
    @ 2015-03-09 11:08:47

    好久没有一次AC了。。
    var dist:array[0..2005] of longint;
    use:array[0..2005] of boolean;
    map,cost:array[0..2001,0..2001] of longint;
    i,n,a,b,r:longint;

    function min(a,b:longint):longint;
    begin
    if a<b then exit(a)
    else exit(b);
    end;

    procedure dijkstra;
    var tip,i,j,max,pos:longint;
    begin
    for i:=1 to n do dist[i]:=0;
    dist[1]:=100000000;
    for i:=1 to n-1 do
    begin
    max:=0;
    for j:=1 to n do
    if not use[j] then
    if dist[j]>max then
    begin
    max:=dist[j];
    pos:=j;
    end;
    use[pos]:=true;
    for j:=1 to map[pos,0] do
    begin
    tip:=min(dist[pos],cost[pos,map[pos,j]]);
    if tip>dist[map[pos,j]] then
    dist[map[pos,j]]:=tip;
    end;
    end;
    end;

    begin
    //assign(input,'P1391.in');
    //assign(output,'P1391.out');
    //reset(input);
    //rewrite(output);
    readln(n);
    readln(a,b,r);
    while (a<>0) and (b<>0) and (r<>0) do
    begin
    inc(map[a,0]);
    map[a,map[a,0]]:=b;
    cost[a,b]:=r;
    readln(a,b,r);
    end;
    dijkstra;
    for i:=2 to n do writeln(dist[i]);
    //close(input);
    //close(output);
    end.

  • 0
    @ 2015-03-05 11:17:27

    #include <limits.h>
    #include <stdio.h>
    #include <string.h>
    #include <queue>
    #include <vector>
    const int maxV = 2020;
    using std::vector;
    using std::deque;
    struct edge {
    int w, t;
    edge (int _t = 0, int _w = 0) {
    w = _w;
    t = _t;
    }
    };
    int V;
    int f[maxV];
    bool vis[maxV];
    vector<edge> s[maxV];
    void init () {
    int x, y, z;
    scanf("%d %d %d %d", &V, &x, &y, &z);
    while (x != 0 || y != 0 || z != 0) {
    s[x].push_back(edge(y, z));
    scanf("%d %d %d", &x, &y, &z);
    }
    }
    inline int min (int a, int b) {
    return (a < b ? a : b);
    }
    void spfa (int source) {
    int cur, curTo, curW;
    memset(f, 0, sizeof(f));
    memset(vis, false, sizeof(vis));
    deque<int> q;
    q.push_back(source);
    vis[source] = true;
    f[source] = INT_MAX;
    while (!q.empty()) {
    cur = q.front();
    q.pop_front();
    vis[cur] = false;
    for (int i = 0, size = s[cur].size(), t; i < size; ++i) {
    curTo = s[cur][i].t;
    curW = s[cur][i].w;
    t = min(curW, f[cur]);
    if (f[curTo] < t) {
    f[curTo] = t;
    if (!vis[curTo]) {
    vis[curTo] = true;
    q.push_back(curTo);
    }
    }
    }
    }
    }
    int main () {
    init ();
    spfa (1);
    for (int i = 2; i <= V; ++i)
    printf("%d\n", f[i]);
    return 0;
    }
    相当简单的spfa

信息

ID
1391
难度
6
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
2948
已通过
815
通过率
28%
被复制
5
上传者