题解

104 条题解

  • 0
    @ 2007-06-05 12:48:52

    brick同学

    您知道前向星这个东西么?

  • 0
    @ 2006-10-10 16:03:23

    稍微加点剪枝的迭代广搜足够了……这题数据太弱

  • 0
    @ 2006-05-05 21:05:43

    n(

  • -1
    @ 2017-05-11 12:51:37

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=5001;
    int dist[maxn],tired[maxn],in[maxn];
    struct edge{
    int to;
    int v;
    int t;
    };
    int k;
    vector<edge> e[400001];
    queue<int> q;
    void init(){
    for(int i=0;i<maxn;i++){
    dist[i]=1e9;
    tired[i]=1e9;
    }

    }
    void spfa(int s){
    dist[s]=0;
    tired[s]=0;
    in[s]=1;
    q.push(s);
    while(!q.empty()){
    int h=q.front();
    in[h]=0;
    q.pop();
    for(int i=0;i<e[h].size();i++){
    if(dist[e[h][i].to]>dist[h]+e[h][i].v&&tired[h]+e[h][i].t<=k){
    dist[e[h][i].to]=dist[h]+e[h][i].v;
    tired[e[h][i].to]=tired[h]+e[h][i].t;
    if(!in[e[h][i].to]){
    in[e[h][i].to]=1;
    q.push(e[h][i].to);
    }
    /*if(tired[h]+e[h][i].t>k){
    continue;
    }
    else{
    tired[e[h][i].to]=tired[h]+e[h][i].t;
    if(!in[e[h][i].to]){
    in[e[h][i].to]=1;
    q.push(e[h][i].to);
    }
    }*/
    /*if(!in[e[h][i].to]){
    in[e[h][i].to]=1;
    q.push(e[h][i].to);
    }*/
    }
    }
    }
    }
    int n,m;
    int main(){
    int a,b,c,d;
    edge p,p1;
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++){
    cin>>a>>b>>d>>c;
    p.to=b;
    p.v=c;
    p.t=d;
    p1.to=a;
    p1.v=c;
    p1.t=d;
    e[a].push_back(p);
    e[b].push_back(p1);
    }
    int st,end;
    cin>>st>>end;

    cin>>k;
    spfa(st);
    if(dist[end]==1e9)cout<<"-1";
    else
    cout<<dist[end];
    return 0;
    }

  • -1
    @ 2016-11-30 16:04:11

    ###****裸的爆搜可过****
    ```c++
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 196288 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 196284 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 196288 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 196288 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 196284 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 196288 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 196284 KiB, score = 10
    测试数据 #7: Accepted, time = 125 ms, mem = 196284 KiB, score = 10
    测试数据 #8: Accepted, time = 171 ms, mem = 196284 KiB, score = 10
    测试数据 #9: Accepted, time = 343 ms, mem = 196284 KiB, score = 10
    Accepted, time = 715 ms, mem = 196288 KiB, score = 100
    代码
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using std :: min;
    const int INF = 0xffffff;
    int n,m,MIN = INF,k,start,end;
    bool vis[5001];
    struct map {
    int c,d;
    }v[5001][5001];
    inline void input() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= n;i++)
    for (int j = 1;j <= n;j++) v[i][j].c = v[i][j].d = INF;
    for (int i = 1;i <= m;i++) {
    int x,y;
    scanf("%d%d",&x,&y);
    scanf("%d%d",&v[x][y].c,&v[x][y].d);
    v[y][x] = v[x][y];
    }
    scanf("%d%d",&start,&end);
    scanf("%d",&k);
    }
    inline void dfs(int now,int sum,int d) {
    if (d > MIN || sum > k) return;
    if (now == end) {
    MIN = min(MIN,d);
    return;
    }
    for (int i = 1;i <= n;i++)
    if (!vis[i] && v[now][i].d != INF && v[now][i].c != INF) {
    vis[i] = true;
    dfs(i,sum+v[now][i].c,d+v[now][i].d);
    vis[i] = false;
    }
    }
    inline void work() {
    memset(vis,false,sizeof(vis));
    vis[start] = true;
    dfs(start,0,0);
    if (MIN == INF) printf("-1");
    else printf("%d",MIN);
    }
    int main() {
    input();
    work();
    return 0;
    }
    ```

  • -1
    @ 2016-11-18 09:33:51

    裸spfa
    #include<iostream>
    #include<cstdio>
    #include<queue>
    using namespace std;
    #define maxn 99999999
    struct edge{
    int u;
    int val;
    int w;
    edge *link;
    };
    edge graph[9000];
    edge p[90000];
    queue<int> q;
    int n,m,op,ed;
    int num;
    int sum;
    int d[9000];
    int t[9000];
    int visit[9000];
    void addedge(int v,int u,int x,int val){
    edge *k=&p[num];
    k->u=u;
    k->val=val;
    k->w=x;
    k->link=graph[v].link;
    graph[v].link=k;
    num++;
    }
    void spfa(int s){
    visit[s]=1;
    d[s]=0;
    q.push(s);
    while(!q.empty()){
    int u=q.front();
    q.pop();
    visit[u]=0;
    for(edge *l=graph[u].link;l!=NULL;l=l->link){
    if(t[u]+l->w<=sum){
    if(d[l->u]>d[u]+l->val){
    d[l->u]=d[u]+l->val;
    t[l->u]=t[u]+l->w;
    if(visit[l->u]==0){
    visit[l->u]=1;
    q.push(l->u);
    }
    }
    }
    }
    }
    }
    int main(){
    int v,u,x,val;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    graph[i].link=NULL;
    d[i]=maxn;
    visit[i]=0;
    t[i]=0;
    }
    for(int i=1;i<=m;i++){
    scanf("%d %d %d %d",&v,&u,&x,&val);
    addedge(v,u,x,val);
    addedge(u,v,x,val);
    }
    cin>>op>>ed;
    cin>>sum;
    spfa(op);
    if(d[ed]!=maxn)
    cout<<d[ed]<<endl;
    else
    cout<<"-1";
    return 0;
    }

  • -1
    @ 2016-11-17 21:37:19

    预处理:终点开始spfa 获得每个点到终点的最小所需体力值
    起点dfs 可行性剪枝 最优性剪枝
    --第一遍没spfa,过了9个点
    #include <cstdio>
    #include <queue>
    #define INF 439643966

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

    int n,m,START,END,E,ans=INF,vis[5100]={0},top=0;
    edge graph[5100]={0};
    edge node[81000];

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

    void build(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    int u,v,c,d;
    scanf("%d%d%d%d",&u,&v,&c,&d);
    add(u,v,c,d);
    add(v,u,c,d);
    }
    scanf("%d%d%d",&START,&END,&E);
    }

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

    void spfa(int u){
    for(int i=1;i<=n;i++)
    dist[i]=INF;
    dist[u]=0;
    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){
    if(dist[l->v]>dist[t]+l->c){
    dist[l->v]=dist[t]+l->c;
    if(!inque[l->v]){
    q.push(l->v);
    inque[l->v]=1;
    }
    }

    l=l->link;
    }

    }

    }

    void dfs(int u,int c,int d){
    vis[u]=1;
    if(c+dist[u]>E)
    return;
    if(u==END){
    ans=ans<d?ans:d;
    return;
    }
    if(d>=ans)
    return;
    edge *l=graph[u].link;
    while(l){
    dfs(l->v,c+l->c,d+l->d);
    l=l->link;
    }
    vis[u]=0;
    }

    int main(){
    build();
    spfa(END);
    dfs(START,0,0);
    if(ans==INF)
    printf("-1");
    else
    printf("%d",ans);

    return 0;
    }

  • -1
    @ 2016-10-15 10:47:31

    第二组 WA 什么鬼?
    求教!

  • -1
    @ 2016-10-09 18:48:50

    拆点建图spfa+哈希表。由于懒用了map。不过也是100ms In totle

    #include <bits/stdc++.h>
    using namespace std;
    
    struct p {
        long to, len, next, kil;
    }edge[100001];
    long head[5005], top = 0;
    void push(long i, long j, long kil, long len)
    {
        edge[++top].to = j;
        edge[top].len = len;
        edge[top].kil = kil;
        edge[top].next = head[i];
        head[i] = top;
    }
    long dis[5005];
    
    long n, m, s, t, lif;
    #define gr make_pair
    #define po pair<long, long>
    queue<po > que; // point, life
    set<po> exi;
    
    void spfa()
    {    
        memset(dis, 127, sizeof dis);
        dis[s] = 0;
        exi.insert(gr(s, lif));
        for (que.push(gr(s, lif)); !que.empty(); ) {
            po k = que.front(); que.pop(); exi.erase(k);
            //cout << k.first << " " << k.second << endl;
            for (int i = head[k.first]; i; i = edge[i].next) {
                int to = edge[i].to, kil = edge[i].kil, len = edge[i].len;
                if (k.second >= kil && dis[to] > dis[k.first] + len) {
                    dis[to] = dis[k.first] + len;
                    if (!exi.count(gr(to, k.second-kil))) {
                        exi.insert(gr(to, k.second-kil));
                        que.push(gr(to, k.second-kil));
                    }
                }
            }
        }
    }
    
    int main()
    {
        scanf("%ld%ld", &n, &m);
        for (int i = 1; i <= m; i++) {
            long a, b, c, d;
            scanf("%ld%ld%ld%ld", &a, &b, &c, &d);
            push(a, b, c, d);
            push(b, a, c, d);
        }
        cin >> s >> t >> lif;
        spfa();
        if (dis[t] <= 1000000000) 
            cout << dis[t] << endl;
        else
            cout << -1 << endl;
        return 0;
    }
    
  • -1
    @ 2016-07-24 21:37:19

    终点开始SFPA算出体力最小值
    起点开始DFS,可行性剪枝+最优剪枝
    #include <cstdio>
    #include <queue>
    #define INF 999999999

    struct edge{
    int v,val,e;
    edge *link;
    };

    int n,m,S,K,T,top=0;
    edge graph[5050]={0},node[80080];

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

    void build(){
    scanf("%d%d",&n,&m);
    int u,v,e,val;
    for(int i=1;i<=m;i++){
    scanf("%d%d%d%d",&u,&v,&e,&val);
    addedge(u,v,e,val);
    addedge(v,u,e,val);
    }
    scanf("%d%d%d",&S,&T,&K);
    }
    //SPFA:
    int en[5050],inque[5050]={0};
    std::queue<int> q;

    void spfa(int u){
    for(int i=1;i<=n;i++)
    en[i]=INF;
    int t;
    edge *l;
    en[u]=0;
    q.push(u),inque[u]=1;
    while(!q.empty()){
    t=q.front();
    q.pop(),inque[t]=0;
    l=graph[t].link;
    while(l){

    if(en[t]+l->e<en[l->v]){
    en[l->v]=en[t]+l->e;
    if(!inque[l->v]){
    q.push(l->v);
    inque[l->v]=1;
    }

    }
    l=l->link;
    }
    }

    }

    //DFS:
    int ans=INF,vis[50050]={0};

    void dfs(int u,int dist,int e){
    if(u==T){
    ans=ans<dist?ans:dist;
    return;
    }
    edge *l=graph[u].link;
    while(l){
    if(dist>ans||en[l->v]>e-l->e)
    goto q;
    if(!vis[l->v]){
    vis[l->v]=1;
    dfs(l->v,dist+l->val,e-l->e);
    vis[l->v]=0;
    }
    q: l=l->link;
    }

    }

    int main(){
    freopen("in.txt","r",stdin);
    build();
    spfa(T);
    if(en[S]>K){
    printf("-1");
    return 0;
    }
    dfs(S,0,K);
    printf("%d",ans);
    return 0;
    }

  • -1
    @ 2015-10-03 17:26:33

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<queue>
    #include<map>
    #include<vector>
    using namespace std;
    int a,b;
    int k;
    int o,p;
    int sum=1000000;
    int vis[5000];
    struct point{
    int x,step,layer;
    point(int x=0,int step=0,int layer=0):x(x),step(step),layer(layer){}

    };
    vector<int>qq[4000];
    int yu[5000][5000];
    int d[5000][5000];
    void ans()
    {
    memset(vis,0,sizeof(vis));
    queue<point>q;
    point u(o,0,0);
    q.push(u);
    point end_point(p);
    while(!q.empty())
    {

    point u=q.front();
    q.pop();
    int x=u.x;
    int step=u.step;
    int layer=u.layer;
    if(x==end_point.x){sum=min(sum,step);}
    else {
    for(int i=0;i<qq[x].size();i++)
    {

    if(step+d[x][qq[x][i]]<=sum&&layer+yu[x][qq[x][i]]<=k){q.push(point(qq[x][i],step+d[x][qq[x][i]],layer+yu[x][qq[x][i]]));}

    }

    }

    }

    }
    int main()
    {
    cin>>a>>b;
    for(int i=0;i<b;i++)
    {
    int q,w,e,r;
    cin>>q>>w>>e>>r;

    qq[q].push_back(w);
    yu[q][w]=e;
    yu[w][q]=e;
    d[q][w]=r;
    d[w][q]=r;
    qq[w].push_back(q);
    }
    cin>>o>>p;
    cin>>k;
    ans();
    if(sum==1000000)cout<<"-1";
    else{cout<<sum;}
    return 0;

    }

    为什么只有七组过

  • -1
    @ 2015-08-03 12:52:39

    program a1082;
    type pp=^re;
    re=record
    a,b,c:longint;
    d:pp;
    end;
    var
    i,j,k,l,s,t,n,m,ii,jj,kk,ll:longint;
    pa:array[0..10000]of pp;
    aa,ss:array[0..10000]of int64;
    dui:array[0..1000000]of longint;

    procedure ff(x,y,z,zz:longint);
    var
    p:pp;
    begin
    p:=pa[x];
    new(pa[x]);
    pa[x]^.c:=z;
    pa[x]^.b:=zz;
    pa[x]^.a:=y;
    pa[x]^.d:=p;
    end;

    procedure spfa(x,y:longint);
    var
    i,j,kk,ll,l,r:longint; p:pp;
    begin
    fillchar(aa,sizeof(aa),$7f div 3);
    dui[1]:=x; l:=0; r:=1; aa[x]:=0;
    while l<=r do
    begin
    inc(l);
    kk:=dui[l];
    p:=pa[kk];
    while p<>nil do
    begin
    if (aa[p^.a]>aa[kk]+p^.c)
    or((aa[p^.a]=aa[kk]+p^.c)and(ss[p^.a]>ss[kk]+p^.b)) then
    begin
    aa[p^.a]:=aa[kk]+p^.c;
    ss[p^.a]:=ss[kk]+p^.b;
    inc(r);
    dui[r]:=p^.a;
    end;
    p:=p^.d;
    end;
    end;
    if aa[y]>k then begin writeln(-1); halt; end else writeln(ss[y]);
    end;

    begin
    readln(n,m);
    for i:=1 to m do
    begin
    readln(ii,jj,kk,ll);
    ff(ii,jj,kk,ll);
    ff(jj,ii,kk,ll);
    end;
    readln(s,t);
    readln(k);
    spfa(s,t);
    end.

  • -1
    @ 2015-08-03 10:48:09

    program aaaaaa;
    type pp=record
    a,b,c,d:longint;
    end;
    var
    i,j,k,l,n,m,s,t,ii,jj,kk,ll,ans,an:longint;
    a:array[0..5000,0..1500]of pp;
    b:array[0..5000]of boolean;

    procedure dfs(x,y,z:longint);
    var
    i,j,l,kk:longint;
    begin
    if x=t then
    begin
    // writeln(y,' ',z);
    if (y<=k)and(z<ans) then
    begin
    ans:=z;
    an:=y;
    end;
    exit;
    end;
    if y>k then exit;
    if z>ans then exit;
    for i:=1 to a[x,0].d do
    if b[a[x,i].a]=false then
    begin
    b[a[x,i].a]:=true;
    y:=y+a[x,i].b;
    z:=z+a[x,i].c;
    dfs(a[x,i].a,y,z);
    b[a[x,i].a]:=false;
    y:=y-a[x,i].b;
    z:=z-a[x,i].c;
    end;
    end;
    begin

    readln(n,m);
    for i:=1 to m do
    begin
    readln(ii,jj,kk,ll);
    inc(a[ii,0].d);
    a[ii,a[ii,0].d].a:=jj;
    a[ii,a[ii,0].d].b:=kk;
    a[ii,a[ii,0].d].c:=ll;
    inc(a[jj,0].d);
    a[jj,a[jj,0].d].a:=ii;
    a[jj,a[jj,0].d].b:=kk;
    a[jj,a[jj,0].d].c:=ll;
    end;
    readln(s,t);
    readln(k);
    ans:=maxlongint;
    fillchar(b,sizeof(b),false);
    b[s]:=true;
    dfs(s,0,0);
    // writeln(ans);
    // writeln(an);
    if ans=maxlongint then writeln(-1) else writeln(ans);
    end.

  • -1
    @ 2015-01-31 13:43:00

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 1812 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 1812 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 1812 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 1820 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 1812 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 1816 KiB, score = 10
    Accepted, time = 60 ms, mem = 1820 KiB, score = 100

  • -1
    @ 2014-10-15 15:12:40

    双SPFA处理体力MIN,时间MIN,然后最优性剪枝。

  • -1
    @ 2014-10-03 15:38:44

    下面情况未考虑:
    4 4
    1 3 5 2
    1 2 1 2
    2 3 2 2
    3 4 2 1
    1 4
    6
    答案是:5
    诸位测试一下自己的通过代码。

  • -1
    @ 2014-04-26 14:39:42

    应该是dfs加剪枝

  • -1
    @ 2014-03-28 19:57:00

    测试数据 #0: Accepted, time = 62 ms, mem = 98716 KiB, score = 10
    测试数据 #1: Accepted, time = 62 ms, mem = 98720 KiB, score = 10
    测试数据 #2: Accepted, time = 78 ms, mem = 98716 KiB, score = 10
    测试数据 #3: Accepted, time = 78 ms, mem = 98720 KiB, score = 10
    测试数据 #4: Accepted, time = 78 ms, mem = 98716 KiB, score = 10
    测试数据 #5: Accepted, time = 78 ms, mem = 98720 KiB, score = 10
    测试数据 #6: Accepted, time = 78 ms, mem = 98700 KiB, score = 10
    测试数据 #7: Accepted, time = 312 ms, mem = 98716 KiB, score = 10
    测试数据 #8: Accepted, time = 171 ms, mem = 98716 KiB, score = 10
    测试数据 #9: Accepted, time = 733 ms, mem = 98720 KiB, score = 10
    这也太惨不忍睹了吧!!!100多行的代码啊! 写了三个SPFA!

    • @ 2015-04-26 20:19:49

      不怕。3个spfa只是修改细节,只要复制粘贴就好了

    • @ 2015-06-28 09:42:46

      是哪三个spfa

  • -1
    @ 2013-12-28 15:43:47

    这题我的思路是预处理+枚举:
    不妨记dp[i][0][0]是从源点到i时最少体力对应的(体力,时间)花费, dp[i][0][1]是从源点到i时最小时间对应的(体力,时间)花费, dp[i][1][0]是从汇点到i时最小体力对应的(体力,时间)花费, dp[i][1][1]是从汇点到i时最小时间对应的(体力,时间)花费。那么就会出现四种情况:

    dp[i][0][0]+dp[i][1][0]: 从源到i的最小体力和从i到汇点的最小体力下的花费

    dp[i][0][0]+dp[i][1][1]: 从源到i的最小体力和从i到汇点的最小时间下的花费

    dp[i][0][1]+dp[i][1][0]: 从源到i的最小时间和从i到汇点的最小体力下的花费

    dp[i][0][1]+dp[i][1][1]: 从源到i的最小时间和从i到汇点的最小时间下的花费

    因此, 枚举点i, 即可算出从源到汇的满足体力限制的最小时间。

  • -1
    @ 2013-12-16 20:09:26

    共同学习
    发一个邻接表的代码,请多指教
    #include<stdio.h>
    #include<queue>
    #include<string.h>
    #include <malloc.h>
    #define MAXN 5001
    #define INF 0x3f3f3f3f
    using namespace std;
    struct Edge;
    struct Node
    {
    Edge *next;
    bool used;
    int idx;
    }V[MAXN];
    struct Edge
    {
    Edge *next;
    Node *to;
    int tl,len;
    };
    int dis[MAXN],T[MAXN],n,m,s,t,k;
    void addEdge(struct Node *A,struct Node *B,int tl,int len)
    {
    struct Edge t = (struct Edge)malloc(sizeof(struct Edge));
    t->next = A->next;
    t->to = B;
    t->tl = tl;
    t->len = len;
    A->next = t;

    }
    void spfa(int x)
    {
    memset(dis,0x3f,sizeof(dis));
    queue<Node*>Q;
    V[x].used=true;
    dis[x]=0;
    Q.push(&V[x]);
    while(!Q.empty())
    {
    Node* tmp=Q.front();
    Q.pop();
    for(struct Edge *e=tmp->next;e;e=e->next)
    {
    if(dis[tmp->idx]+e->len<dis[e->to->idx]&&T[tmp->idx]+e->tl<=k)
    {
    dis[e->to->idx]=dis[tmp->idx]+e->len,
    T[e->to->idx]=T[tmp->idx]+e->tl;
    if(!e->to->used)
    {
    Q.push(e->to),
    e->to->used=true;
    }

    }
    }
    tmp->used=false;
    }
    if(dis[t] == INF)
    {
    printf("-1\n");

    }else
    {
    printf("%d\n",dis[t]);
    }

    return;
    }
    int main()
    {
    int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)V[i].idx=i;
    for(i=1;i<=m;++i)
    {
    int x,y,c,d;
    scanf("%d%d%d%d",&x,&y,&c,&d);
    addEdge(&V[x],&V[y],c,d);
    addEdge(&V[y],&V[x],c,d);
    }
    scanf("%d%d%d",&s,&t,&k);
    spfa(s);
    }

信息

ID
1082
难度
7
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
2117
已通过
488
通过率
23%
被复制
5
上传者