0基础刷图论最短路 2（从ATcoder 0分到1800分）

AT最短路刷题2（本文难度rated 1000~ 1200）

题目来源：Atcoder
题目收集：
https://atcoder-tags.herokuapp.com/tags/Graph/Shortest-Path
（里面按tag分类好了Atcoder的所有题目，类似cf）
（访问需要魔法）
这算是一个题单，各位有兴趣可以按照这个顺序来刷。
我的代码仅供参考。
会提示关键性质和步骤。 部分有注释。
洛谷、知乎、可以搜到题解。

1-Souvenir

https://atcoder.jp/contests/abc286/tasks/abc286_e

双关键字最短路。

#include
using namespace std;
#define int long long
#define endl 'n'
#define PII pairint,int>
#define INF 1e18

int dist[301][301];
int value[301][301];
int a[301];
char s[301][301];
int n;



void dijkstra(int start){
    vectorbool> flag(n+1);
    for(int i=1;in;i++){
        dist[start][i]=INF;
    }
    dist[start][start]=0;

    priority_queuePII,vectorPII>,greaterPII>> q;

    q.push({0,start});

    value[start][start]=a[start];
    dist[start][start]=0;



    while(q.size()){
        int u = q.top().second;
        q.pop();

        if(flag[u])continue;
        flag[u]=1;

        for(int i=1;in;i++){
            if(i==u)continue;
            if(s[u][i]=='N')continue;
            if(dist[start][i]>dist[start][u]+1){
                dist[start][i] = dist[start][u]+1;
                value[start][i] = value[start][u] + a[i];
                q.push({dist[start][i],i});
            }
            else if(dist[start][i]==dist[start][u]+1 and value[start][i]value[start][u]+a[i]){
                value[start][i] = value[start][u] + a[i];
                q.push({dist[start][i],i});
            }

        }
    }
}
void slove(){
    cin>>n;
    for(int i=1;in;i++){
        cin>>a[i];
    }

    for(int i=1;in;i++)
        for(int j=1;jn;j++)
            cin>>s[i][j];

    for(int i=1;in;i++){
        dijkstra(i);
    }

    int Q;
    cin>>Q;
    while(Q--){
        int u,v;
        cin>>u>>v;
        if(dist[u][v]==INF)cout"Impossible"endl;
        else coutdist[u][v]' 'value[u][v]endl;
    }
}

signed main(){
    slove();
}

2-Train

https://atcoder.jp/contests/abc192/tasks/abc192_e

最短路板子

/*对于每一条边：
火车发动的时间是： t = kx
所以可以开两个数组。

数组1，记录 ai --> bi 城市的火车发车间隔，
数组2，记录 ai --> bi 代价

如何写最短路？

数组3记录 从起点到各点的最小值。
*/

#include
using namespace std;
#define int long long
#define endl 'n'
#define PII pairint,int>
#define INF 1e18


const int N = 1e5+7;
struct node{
    int v;
    int w;
    int k;
};

vectorvectornode>> g(N);
int dist[N];
bool flag[N];
int n,m;
void dijkstra(int x){

    for(int i=1;in;i++)dist[i]=INF;
    dist[x]=0;
    priority_queuePII,vectorPII>,greaterPII>> q;
    q.push({0,x});

    while(q.size()){
        int u = q.top().second;
        q.pop();
        if(flag[u])continue;
        flag[u]=1;
        for(auto i:g[u]){ //枚举能去的所有城市
            int v = i.v , w = i.w , k = i.k;
            int now = dist[u]; //当前时刻
            // 检查此时是不是刚好发车
            if(now%k==0){
                //如果刚好发车，那么直接加上边权
                if(dist[v]>dist[u]+w){
                    dist[v] = dist[u]+w;
                    q.push({dist[v],v});
                }
            }
            else{ //只能等下一班车
                int next = now / k + 1;
                now = k*next;
                if(dist[v]>now+w){
                    dist[v]=now+w;
                    q.push({dist[v],v});
                }
            }

        }
    }
}

void slove(){
    cin>>n>>m;
    int x,y;
    cin>>x>>y;

    for(int i=1;im;i++){
        int u,v,w,k;
        cin>>u>>v>>w>>k;
        g[u].push_back(node{v,w,k});
        g[v].push_back(node{u,w,k});
    }

    dijkstra(x);

    if(dist[y]==INF)cout-1endl;
    else coutdist[y]endl;

}

signed main(){
    slove();
}

3-バスと避けられない運命

https://atcoder.jp/contests/abc012/tasks/abc012_4

spfa板子

#include
using namespace std;
#define int long long
#define endl 'n'
#define PII pairint,int>
#define INF 1e18
const int N = 305;
int dist[N][N];
void slove(){
    int n,m;
    cin>>n>>m;
    for(int i=1;in;i++){
        for(int j=1;jn;j++){
            dist[i][j]=INF;
        }
        dist[i][i]=0;
    }

    for(int i=1;im;i++){
        int u,v,w;
        cin>>u>>v>>w;
        dist[u][v]=w;
        dist[v][u]=w;
    }

    for(int k=1;kn;k++){
        for(int i=1;in;i++){
    服务器托管        for(int j=1;jn;j++){
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }

    int ans = INF;
    for(int i=1;in;i++){
        int cnt=0;
        for(int j=1;jn;j++){
            if(dist[i][j]==INF)continue;
            cnt = max(cnt,dist[i][j]);
        }
        ans = min(cnt,ans);
    }
    coutansendl;
}

signed main(){
    slove();
}

4-Crystal Switches

https://atcoder.jp/contests/abc277/tasks/abc277_e

/*

给你一张图：
如果边权是0，则代表开关关闭，不能通过
如果边权是1，代表开关打开，能通过

对于每个结点，记录：

1、结点编号
2、当前结点被反转
3、步数

从起点开始bfs
遍历所有u能去的点，
如果边权是0：
        打开开关，加入状态： node = { v , 1 , step+1 }
如果边权是1：
        不管开关，加入状态： node = { v , 0 , step+1 }

接下来对于v，如果图中所有边被反转：

那么边权原来是1的，现在就是0
        所以还是要操作开关，node = { i , 0 , step+1 }
如果边权原来是0的，现在就是1
        所以不需要操作开关，node = { i , 1 , step+1 }

        */


#include
using namespace std;
#define int long long
#define endl 'n'
#define PII pairint,int>
#define INF 1e18

struct node{
    int u;
    int step;
    int opt;
    bool operator  (node b)const{
        return step>b.step;
    }
};

struct gg{
    int v;
    int w; //边权
};

const int N = 2e5+7;
vectorgg> g[N];//存图
vectorint> s(N); //哪些结点上面有开关
int n,m;

int flag[N][2]; // 每个结点的每种状态只访问一次。
int dist[N]; //1到n的最短路

void dijkstra(){
    for(int i=1;in;i++)dist[i]=INF;
    dist[1]=0;

    priority_queuenode> q;
    node now;
    now.u = 1;
    now.opt=0;
    now.step=0;
    q.push(now);

    while(q.size()){
        int u = q.top().u;
        int step = q.top().step;
        int opt = q.top().opt;
        q.pop();

        if(flag[u][opt])continue;
        flag[u][opt]=1;

        if(u==n){
            coutstependl;
            return;
        }

        node nxt;
        for(auto i:g[u]){
            int v = i.v;
            int w = i.w;

            //第一种情况，当前图没被反转，且该边能通过
            if(opt==0 and w==1)
            {
                nxt.step = step+w;
                nxt.u = v;
                nxt.opt = opt;
                q.push(nxt);

            }
            else if(opt==0 and w==0)//第二种情况，当前图没被反转，但该边不能通过
            {
                //检查这个点是否有开关
                if(s[u]==1)
                {
                    nxt.step = step +1;
                    nxt.u = v;
                    nxt.opt = 1;
                    q.push(nxt);
                }
                // 如果此路不通，且u没有开关，那么爱莫能助
            }
            else if(opt==1 and w==1) //如果图被反转了一次，此时w=1 相当于不能通过
            {
                if(s[u]==1) //如果有开关，那么再反转一次全图
                {
                    nxt.step = step+1;
                    nxt.u = v;
                    nxt.opt = 0;
                    q.push(nxt);
                }
            }
            else if(opt==1 and w==0) //如果地图被反转1次，此时w=0，代表可以通过
            {
                nxt.step = step+1;
                nxt.u = v;
        服务器托管        nxt.opt = opt;
                q.push(nxt);
            }
        }
    }


    cout-1endl;

}
void slove(){
    int k;
    cin>>n>>m>>k;
    for(int i=1;im;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(gg{v,w});
        g[v].push_back(gg{u,w});
    }

    for(int i=1;ik;i++){
        int t;
        cin>>t;
        s[t]=1;
    }

    dijkstra();

}

signed main(){
    slove();
}

5-Shortest Path Queries 2

https://atcoder.jp/contests/abc208/tasks/abc208_d

纯板子，呆题

#include
using namespace std;
#define int long long
#define endl 'n'
#define PII pairint,int>
#define INF 1e18

const int N = 405;
int dist[N][N];

void slove(){

    int n,m;
    cin>>n>>m;

    for(int i=1;in;i++)
    {
        for(int j=1;jn;j++)
        {
            dist[i][j]=INF;
        }
        dist[i][i]=0;
    }



    for(int i=1;im;i++){
        int u,v,w;
        cin>>u>>v>>w;
        dist[u][v]=w;
    }

    int ans = 0;
    for(int k=1;kn;k++){
        for(int i=1;in;i++){
            for(int j=1;jn;j++){
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
                if(dist[i][j]!=INF){
                    ans += dist[i][j];
                }
            }
        }
    }
    coutansendl;
}

signed main(){
    slove();
}

6- Jumping Takahashi 2

https://atcoder.jp/contests/abc257/tasks/abc257_d

二分+bfs

/*
 题目的意思是：

 让我们选择一个起始的蹦床。
 能从这个蹦床去到所有的蹦床的最小跳跃高度。

 然后找到这些最小跳跃高度中最小的那一个。

 我们可以二分跳跃高度 s
 然后枚举每一个起点。

 判断，这个跳跃高度是否能跳到任意一个蹦床。

 现在，问题就是，如何写check函数？

 可以写一个bfs，求连通性。
 如果最终连通，那么这个s是ok的

 时间复杂度： O(n^2 * log(1e10))

*/



#include
using namespace std;
#define int long long
#define endl 'n'
#define PII pairint,int>
#define INF 1e18

struct node{
    int id;
    int x;
    int y;
    int p;
};

const int N =201;
node a[N];

int ans = INF; //答案
int n;
bool flag[201];

bool check(int mid,int start){
    memset(flag,0,sizeof flag);
    queuenode> q;
    q.push(a[start]);

    flag[start]=1;
    while(q.size()){
        int x = q.front().x;
        int y = q.front().y;
        int p = q.front().p;
        q.pop();

        node nxt;
        for(int i=1;in;i++){
            if(flag[i])continue;

            int xx = a[i].x;
            int yy = a[i].y;

            int dist = abs(x-xx)+abs(y-yy);
            if(mid*p>=dist){
                q.push(a[i]);
                flag[i]=1;
            }
        }

    }

    for(int i=1;in;i++){
        if(flag[i]==0)return false;
    }
    return true;
}
void work(int start){

    //二分跳跃高度
    int l=1, r = 1e10;
    while(lr){
        int mid = l+r>>1;
        if(check(mid,start)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    ans = min(ans,l);
}
void slove(){

    cin>>n;
    for(int i=1;in;i++){
        cin>>a[i].x>>a[i].y>>a[i].p;
        a[i].id=i;
    }

    for(int i=1;in;i++){
        work(i);
    }
    coutansendl;
}

signed main(){
    slove();
}

7-Skiing

https://atcoder.jp/contests/abc237/tasks/abc237_e

最长路的处理方法之一：

1、所有边权都乘上-1，然后跑spfa
值得注意的是，此题的时间需要不超过 O(NM)

2、跑不了spfa，只能跑dijkstra
此时必须要从边权的计算方式，题目含义等条件入手。
来消除负权边。（吃经验 or 思维）

/*

    重力势能只与初始状态和末尾状态有关。
    初始状态是h[1],末尾状态是h[i]
    重力势能的变化就是 初状态 - 末状态 = h[1] - h[i]
    但是，这题没有这么简单。
    如果你走上坡路，那么消耗的是同等高度走下坡路的两倍。
    如果你走下坡路，只要你这个点是中间状态，那么一律不需要管，
    因为下坡路的贡献最终都会被抵消，剩下h[1]-[i]

    所以得到一个结论：
    假如初始状态和末尾状态都确定了，那么我们要想让最终答案最大。
    我们就必须使得走的上坡路的总代价越小 （这里说的是绝对值）

    也就是走最短路。

    而由于下坡路是没有影响的，所以下坡路的边权为0
    上坡路的边权 为1倍的  abs(h[u]-h[v])



*/


#include
using namespace std;
#define int long long
#define endl 'n'
#define PII pair
#define INF 1e18
const int N = 2e5+7;

struct node{
    int v;
    int w;
};

vector g[N];

int n,m;
int h[N];
int dist[N];
bool flag[N];
priority_queue,greater> q;


void dijkstra(){
    for(int i=1;idist[u]+w){
                dist[v]=dist[u]+w;
                q.push({dist[v],v});
            }
        }
    }
}
void slove(){
    cin>>n>>m;
    for(int i=1;i>h[i];
    for(int i=1;i>u>>v;
        int w = h[v]-h[u];
        if(w v
            g[u].push_back(node{v,0});
            g[v].push_back(node{u,-w});
        }
        else // u

8-Wizard in Maze

https://atcoder.jp/contests/abc176/tasks/abc176_d

bfs模板题

打的太多了，所以直接贴个答案上去。

#include
#include
#include
using namespace std;

int h, w, ch, cw, dh, dw, dis[1005][1005];
//dis[i][j]表示从(ch, cw)出发到达(i, j)所消耗跳跃魔法次数的最小值
char a[1005][1005];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

struct node
{ //从(ch, cw)出发到达(x, y)所消耗跳跃魔法次数的最小值t
    int x, y, t;
};

dequenode> q;

void bfs()
{
    q.push_front(node{ch, cw, 0});
    dis[ch][cw] = 0;

    while(!q.empty())
    {
        int x = q.front().x, y = q.front().y, t = q.front().t;
        q.pop_front();

        //(x,y)普通移动能达到的子结点插入队首
        for(int i = 0; i  3; i++)
        {
            int x_new = x + dx[i], y_new = y + dy[i];
            if(x_new  1 || x_new > h || y_new  1 || y_new > w) continue;
            if(a[x_new][y_new] == '#') continue;
            if(dis[x_new][y_new]  dis[x][y]) continue;
            q.push_front(node{x_new, y_new, t});
            dis[x_new][y_new] = t;
        }

        //(x,y)跳跃魔法移动能达到的子结点插入队尾
        for(int x_new = x - 2; x_new  x + 2; x_new++)
            for(int y_new = y - 2; y_new  y + 2; y_new++)
            {
                if(x_new  1 || x_new > h || y_new  1 || y_new > w) continue;
                if(a[x_new][y_new] == '#') continue;
                if(dis[x_new][y_new]  dis[x][y] + 1) continue;
                q.push_back(node{x_new, y_new, t + 1});
                dis[x_new][y_new] = t + 1;
            }
    }
}

int main()
{
    cin >> h >> w;
    cin >> ch >> cw;
    cin >> dh >> dw;
    for(int i = 1; i  h; i++)
        for(int j = 1; j  w; j++)
            cin >> a[i][j];

    memset(dis, 0x3f, sizeof(dis));
    bfs();

    if(dis[dh][dw] == 0x3f3f3f3f) cout  -1  endl;
    else cout  dis[dh][dw]  endl;

    return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net