题目：

西西所在的国家有N座城市，每座城市都有一道传送门，城市 i 的传送门通往城市 a[i]。当西西位于城市 i 时，每次他可以执行以下三种操作中的一种：
花费 A 的费用，从城市 i 前往城市 a[i]；
如果 a[i] > 1，可以花费 B 的费用，将 a[i] 的值减少 1；
如果 a[i] < N，可以花费 C 的费用，将 a[i] 的值增加 1。
现在，西西想从城市 1 前往城市 N，那么他至少要花费多少费用？
input：
第一行输入四个整数 N、A、B、C（1 < N <= 10000，1 <= A、B、C <= 100000）。
第二行输入 N 个整数 a[1] 到 a[N]（1 <= a[i] <= N）。
output:
输出一个整数，表示从城市 1 前往城市 N 所花费的最少费用。
sample:
7 1 1 1
3 6 4 3 4 5 6
output
4

思路：

在想着练练熟练度时做的题，花了一个小时想思路，一开始无从下手不知道是搜索还是dp还是贪心，先模拟走第一个，发现其实是规律操作（看似多种操作有无数种不同的情况，其实都是一样的情况），即第一个城市出发去任何其他城市都是要最基本的transfer，然后在此上去非直达的再加上move代价，第一个城市出发后再走第二个一开始以为是从二出发了到剩下的，那就类似于排列组合的递减级别复杂，但发现不对第二次不一定是第二个城市出发，可以是任意一个城市出发到任意一个（都可以往回走和走自己），然后就联系起了矩阵乘法，花了很多时间验证思路是可行的，所以问题抽象为一个城市图矩阵操作（类乘）一次即插入一个中间城市，然后操作是两向量的各个元素相加的最小的一对值。写代码花了一个多小时，用全局还没初始化在初始化函数里直接用全局map的size。。。

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> map;
vector<vector<int>> patt;

int line(int row, int col){
    int min_tempt = 9999;
    for(int k=0;k<map.size();++k){
        int t=patt[row][k]+map[k][col];
        min_tempt = min(min_tempt, patt[row][k]+map[k][col]);
    }
    return min_tempt;
}
void matrix(){
    vector<vector<int>> tempt;
    for(int i=0;i<map.size();++i){
        vector<int> row;
        for(int j=0;j<map.size();++j){
            row.push_back(line(i, j));
        }
        tempt.push_back(row);
    }
    for(int i=0;i<map.size();++i){
        for(int j=0;j<map.size();++j){
            map[i][j] = tempt[i][j];
        }
    }
}
void print(){
    for(int i=0;i<map.size();++i){
        for(int j=0;j<map.size();++j){
            cout<<map[i][j]<<" ";
        }
        cout<<"       ";
        for(int j=0;j<map.size();++j){
            cout<<patt[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
void init(vector<int> row, int a, int b, int c){
    for(int i=0;i<row.size();++i){//这里用了map.size()。。。还以为是下面初始化方式不对
        map.push_back(vector<int>(row.size()));
        patt.push_back(vector<int>(row.size()));
    }
    for(int i=0;i<row.size();++i){
        for(int j=(row[i]-1);j<row.size();++j){
            map[i][j] = a + (j-(row[i]-1))*c;
            patt[i][j] = map[i][j];
        }
        for(int j=(row[i]-1);j>=0;--j){
            map[i][j] = a + (row[i]-j-1)*b;
            patt[i][j] = map[i][j];
        }
    }
    for(int i=0;i<row.size();++i){
        map[i][i] = 0;
        patt[i][i] = 0;
    }
}

int main() {
    int n, a, b, c;
    vector<int> v;
    cin>>n>>a>>b>>c;
    while(n--){
        int tempt;
        cin>>tempt;
        v.push_back(tempt);
    }

    init(v, a, b, c);
    print();
    for(int i=0;i<v.size();++i){
        matrix();
        print();
    }


    return 0;
}

最后的答案是map[0][n-1]上的值，这个样例发现矩阵只在第一次变了一个元素，乍一看以为矩阵没变代码错误找了半天。。。因为他只绕一个城市就是最优答案了。。。

去网上看了，还有一个贪心最短路径思路，没看全但貌似是从n出发的贪心而不是从1出发，1出发贪心每次只能直达访问，肯定不是最优解甚至无解，（move代价高他肯定不会走而无法直达n时这样无解），而从n出发其实是倒着走，最后一个间接城市c到n肯定要是到n最好的一条，然后接着再往前找到c的城市的最好的一条，但用例子就会发现有等同代价的选择且结果并不是任意一条都是最优，所以要加个条件提前到达1的代价最小路线，当都不是到1且代价等同的多个，则直接搜索吧。这里就没细看了。。。有（mei）空再来