2019安徽省程序设计竞赛 D.自驾游(最短路)

这道题最后没过，估计是痛失省一了，现在来补一下，当时思路是对的应该是代码出了问题导致样例没过最后nc的除了2，一直WA

题意：

给一张联通图，有两个导航系统，其中一个系统认为第i条边的权值是Pi，另一个系统认为是Qi（给定Pi和Qi），然后每个导航系统对于每条边i有个判定

其中一个是hero(vi)+Pi>hero(ui)会报警一次，另一个系统是a(vi)+Qi>a(ui)会报警一次，ui是边i的一个结点vi是另一个结点，让求一条两个系统警告次数相加最少的一条路径。

思路：

先从终点n作为起点跑两次最短路，一个按Pi为权值，求出每个节点v的hero(v)，第二次以Qi为权值，求出每个节点v的a(v)。

然后遍历每条边，用警告次数作为权值从1作为起点再跑一次最短路求出结果即可。最短路的求法我用了Dij+堆优化。

这个改正过的代码只过了样例，没法实际测试了，有不对的地方还请大佬指正。

样例数据：

Sample input

5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5

Sample output

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + ;

const int maxm = 5e4 + ;

const int inf = 0x3f3f3f3f;

struct edge{

    int to, wp, wq, ww, next;

} ed[maxm*];

int n, m, head[maxn], tot;

int hero[maxn], a[maxn], dis[maxn];

bool vis[maxn];

inline void add( int u, int v, int p, int q ){

    ed[tot].to = v;

    ed[tot].wp = p;

    ed[tot].wq = q;

    ed[tot].ww = ;

    ed[tot].next = head[u];

    head[u] = tot ++;

}

inline void dij1(int s){

    memset( vis, , sizeof(vis) );

    memset( hero, inf, sizeof(hero) );

    priority_queue< pair<int, int> > q;

    vis[s] = ;

    hero[s] = ;

    q.push( make_pair( , s ) );

    while( !q.empty() ){

        int u = q.top().second;

        q.pop();

        for( int i=head[u]; i!=-; i=ed[i].next ){

            int v = ed[i].to;

            if( hero[v]>hero[u]+ed[i].wp ){

                hero[v] = hero[u]+ed[i].wp;

                if( !vis[v] ){

                    vis[v] = ;

                    q.push( make_pair( -hero[v], v ) );

                }

            }

        }

    }

}

inline void dij2(int s){

    memset( vis, , sizeof(vis) );

    memset( a, inf, sizeof(a) );

    priority_queue< pair<int, int> > q;

    a[s] = ;

    q.push( make_pair( , s ) );

    while( !q.empty() ){

        int u = q.top().second;

        q.pop();

        if( vis[u] ) continue;

        vis[u] = ;

        for( int i=head[u]; i!=-; i=ed[i].next ){

            int v = ed[i].to;

            if( a[v]>a[u]+ed[i].wq ){

                a[v] = a[u]+ed[i].wq;

                q.push( make_pair(-a[v], v) );

            }

        }

    }

}

inline void dij3( int s ){

    memset( vis, , sizeof(vis) );

    memset( dis, inf, sizeof(dis) );

    priority_queue< pair<int, int> > q;

    dis[s] = ;

    q.push( make_pair( , s ) );

    while( !q.empty() ){

        int u = q.top().second;

        q.pop();

        if( vis[u] ) continue;

        vis[u] = ;

        for( int i=head[u]; i!=-; i=ed[i].next ){

            int v = ed[i].to;

            if( dis[v]>dis[u]+ed[i].ww ){

                dis[v] = dis[u]+ed[i].ww;

                q.push( make_pair( -dis[v], v ) );

            }

        }

    }

}

inline void bfs(int s){

    queue<int> q;

    memset( vis, , sizeof(vis) );

    vis[s] = ;

    q.push(s);

    while( !q.empty() ){

        int u = q.front();

        q.pop();

        for( int i=head[u]; i!=-; i=ed[i].next ){

            int v = ed[i].to;

            if( !vis[v] ){

                vis[v] = ;

                if( hero[v]+ed[i].wp>hero[u] ) ed[i].ww ++;

                if( a[v]+ed[i].wq>a[u] ) ed[i].ww ++;

            }

        }

    }

}

int main(){

    // freopen("in.txt", "r", stdin);

    tot = ;

    memset( head, -, sizeof(head) );

    scanf("%d%d", &n, &m);

    for( int i=; i<m; i++ ){

        int u, v, p, q;

        scanf("%d%d%d%d", &u, &v, &p, &q);

        add( u, v, p, q );

        add( v, u, p, q );

    }

    dij1(n);

    dij2(n);

    //注释掉的就是当时写的错误遍历边的代码

    // for( int i=1; i<=n; i++ ){

    //     for( int j=head[i]; j!=-1; j=ed[j].next ){

    //         if( ed[j].wp+hero[ed[j].to]>hero[i] ) ed[j].ww ++;

    //         if( ed[j].wq+a[ed[j].to]>a[i] ) ed[j].ww ++;

    //     }

    // }

    bfs();        //应该从1开始向外bfs遍历边，即可找出正确答案

    dij3();

    printf("%d\n", dis[n]);

    return ;

}

巴特西

2019安徽省程序设计竞赛 D.自驾游(最短路)

最新文章

热门文章