codeJan与旅行

题意

n个城市走m次，问走的路程最短

思路

看完题目还以为是找两个城市最短距离乘 m ，看到有初始位置我还是太年轻了。
因为有初始位置，那在初始时可能有两种情况：
1.走到左边的城市 2.走到右边的城市。这两种情况要分别讨论。
走到任意一个城市后有三种情况：
1.和左边的城市来回走完m次 2.和右边的城市来回走完m次 3. 往左走到一个城市或往右走到一个城市 。
这三种情况直接模拟就好，不过要注意边界

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int maxn = 1e5+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int n,m,p;
ll pos[maxn];//城市的位置
int place;//存最大的小于初始位置的点
ll ans; //走过的距离
bool vis[maxn];//表示是否走过
void dfs(int x,int step,ll cnt){//step表示走过了几个城市 x表示当前位置 ，cnt表示当前走过的距离
    if(step == m){
        ans = min(cnt,ans);
        return ;
    }
    if(x+1 < n){//和右边的城市来回走
        ans = min(ans,cnt+(m-step)*(pos[x+1]-pos[x]));
    }
    if(x > 0){//和左边的城市来回走
        ans = min(ans,cnt+(m-step)*(pos[x]-pos[x-1]));
    }
    if(x+1 < n && vis[x+1]){//去右边城市
        vis[x+1] = false;
        dfs(x+1,step+1,cnt+pos[x+1]-pos[x]);
    }
    if(x >= 0&&vis[x-1]){//去左边城市
        vis[x-1] = false;
        dfs(x-1,step+1,cnt+pos[x]-pos[x-1]);
    } 
}
int main(){
    int t = read();
    while(t--){
         n = read();m = read();p = read();
         place = -1;//初始位置
        for(int i = 0 ; i < n ;++i){
            pos[i] = read();
            if(pos[i]<p) place = i;
        }
        ans = 1e18+5;
        if(place >= 0){
            for(int i = 0 ; i < n ;++i) vis[i] = true;//清空状态
            vis[place] = false;
             dfs( place , 1 , p-pos[place] );
        }
        if(place+1 < n){
            for(int i = 0 ; i < n ;++i) vis[i] = true;
            vis[place+1] = false;
            dfs(place+1 , 1 ,pos[place+1] - p);
        }
        cout<<ans<<endl;
    }
}