/ Vijos / 题库 / 想越狱的小杉 /

题解

98 条题解

  • 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
    @ 2021-10-15 19:23:06

    与其说是在发题解，不如说是在记录学习的过程
    来一篇dijk+堆
    用pair代替结构体
    比较方便
    pair根据第一个值来比较大小

    #include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
const int N=2010;
int n,a,b,c;
vector<P>g[N];
int d[N];
priority_queue<P>q;
void Dijsktra(int s){
    d[s]=2147483647;
    q.push(make_pair(d[s],s));
    while(!q.empty()){
        P f=q.top();q.pop();
        int fv=f.first,fx=f.second;
        if(fv!=d[fx]) continue;
        for(int i=0;i<g[fx].size();i++){
            P y=g[fx][i];
            int yv=y.first,yx=y.second;
            if(d[yx]<min(yv,fv))
                q.push(make_pair(d[yx]=min(yv,fv),yx));
        }
    }
}
int main(){
    scanf("%d",&n);
    while(scanf("%d%d%d",&a,&b,&c)&&(a||b||c))
        g[a].push_back(make_pair(c,b));
    Dijsktra(1);
    for(int i=2;i<=n;i++) printf("%d\n",d[i]);
    return 0;
}

    个人认为码风很好看
    最近学习的疑问：
    1.为什么大佬们喜欢手写链式向前星
    2.加上判断有没有被访问过会更快吗
    2021.10.17
    懂了，是我无知了
    不过邻接表也不会更占空间吧
    是因为数组模拟链式向前星更快还是啥
    不然用邻接表还省个函数和结构体
    有知道的好心人在评论区里教教我呗

  • 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
    @ 2023-08-22 10:35:20

    这道题也可以先离散化边权，再从一边大到小枚举边权、一边用并查集维护连通性吧。。。

  • 0
    @ 2022-07-20 15:35:09 
    /*
我用的是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;
}
  • 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-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.

想越狱的小杉

信息

ID
1391
难度
6
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
2977
已通过
825
通过率
28%
被复制
8
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1