另一个快递机器人

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
 
typedef pair<int, long long> Edge;
typedef map<int, vector<Edge>> Graph;
int n, t, m;
const int MAXD =1000010;
const long long INF=INT64_MAX;
long long pre[MAXD];
Graph G;
 
bool valid_floor(int floor){
    vector<int> vec;
    while(floor){
        vec.push_back(floor%10);
        floor/=10;
    }
    for(int i=0;i<vec.size();i++){
        if(vec[i]==4) return false;
        if(i>0&&vec[i]==1&&vec[i-1]==3) return false;
    }
    return true;
}
 
typedef pair<long long,int> P;
long long dij(int from,int to){
    priority_queue<P, vector<P>, greater<P> > que;
    vector<long long> d(n+1,INF);
    d[from]=0;
    que.push(P(0,from));
    while(!que.empty()){
        P p=que.top();
        que.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(Edge e:G[v]){
            if(d[e.first]>d[v]+e.second){
                d[e.first]=d[v]+e.second;
                que.push(P(d[e.first],e.first));
            }
        }
    }
    if(d[to]==INF){
        printf("-1\n");
        exit(0);
    }
    else return d[to];
}
 
int main()
{
    for(int i=1;i<MAXD;i++){
        if(valid_floor(i)){
            pre[i]=pre[i-1]+1;
        }else{
            pre[i]=pre[i-1];
        }
    }
    scanf("%d%d%d", &n, &t, &m);
    for (int i = 0; i < t; i++)
    {
        int x, y;
        long long d;
        scanf("%d%d%lld", &x, &y, &d);
        G[x].push_back(Edge{y,d});
    }
    int lastb=1,lastr=1;
    long long cost=0;
    for(int i=0;i<m;i++){
        int b,r;
        scanf("%d%d",&b,&r);
        r/=100;
        if(b==lastb){
            cost+=abs(pre[lastr]-pre[r]);
        }else{
            cost+=pre[lastr]-pre[1];
            cost+=dij(lastb,b);
            cost+=pre[r]-pre[1];
        }
        lastb=b;
        lastr=r;
    }
    if(lastb==1){
        cost+=pre[lastr]-pre[1];
    }else{
        cost+=pre[lastr]-pre[1];
        cost+=dij(lastb,1);
    }
    printf("%lld\n",cost);
    return 0;
}

#include <iostream>
#include <vector>
#include <fstream>
#include <map>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
typedef pair<int, int> Edge;
typedef map<int, vector<Edge> > Edges;
int getValue(int start, int v) {
    auto func = [](int x){
        vector<int> vec;
        while (x > 0) {
            vec.push_back(x % 10);
            x /= 10;
        }
        return vec;
    };
    auto find4 = [](vector<int>&vec) {
        for (int i = 0; i < vec.size(); ++i) 
            if (vec[i] == 4)
                return i;
        return -1;
    };
    auto find13 = [](vector<int>& vec) {
        for (int i = 1; i < vec.size(); ++i) {
            if (vec[i] == 1 && vec[i-1] == 3)
                return i-1;
        }
        return -1;
    };
    if (start == v) return 0;
    int min_ = std::min(start, v);
    int max_ = std::max(start, v);
    int n = 0;
    int id4, id13;
    for (int i = min_+1; i <= max_; ) {
        auto vec = func(i);
        int step1 = 0;
        int step2 = 0;
        if ((id4 = find4(vec)) != -1) {
            step1 = 1;
            while (id4--) step1 *= 10;
        }
        if ((id13 = find13(vec)) != -1) { 
            step2 = 1;
            while (id13--) step2 *= 10;
        }
        int step = std::max(step1, step2);
        n += !step;
        i += std::max(step, 1);
    }
    return n;
}
int func(int n, Edges& edges, vector<int>& vex, vector<int>& track) {
    vector< vector<int> > matrix;
    for (int i = 0; i < n; ++i) {
        vector<int> vec(n);
        fill(vec.begin(), vec.end(), -1);
        matrix.push_back(vec);
    }
    for (int i = 0; i < n; ++i) matrix[i][i] = 0;
    for (int i = 0; i < n; ++i) {
        queue<int> q;
        q.push(i);
        vector<int> visited(n);
        visited[i] = 1;
        while (!q.empty()) {
            int x = q.front();
            for (auto e : edges[x]) {
                if (!visited[e.first]) {
                    visited[e.first] = 1;
                    q.push(e.first);
                }
                int y = e.first;
                int d = e.second;
                if (matrix[x][y] == -1) matrix[x][y] = d;
                if (matrix[i][x] + matrix[x][y] < matrix[i][y]) {
                        matrix[i][y] = matrix[i][x] + matrix[x][y];
                }
            }
            q.pop();
        }
    }
    int res = 0;
    int last = 0;
    for (int i = 0; i < track.size(); ++i) {
        if (matrix[last][track[i]] == -1) 
            return -1;
        else {
            res += matrix[last][track[i]];
            res += vex[i];
        }
        last = track[i];
    }
    if (matrix[last][0] == -1) return -1;
    return res + matrix[last][0];
}
int main() {
    int n, t, m;
    cin >> n >> t >> m;
    vector<int> vex;
    vector<int> track;
    Edges edges;
    for (int i = 0; i < t; ++i) {
        int x, y, d;
        Edge e;
        cin >> x >> y >> d;
        e.first = y - 1;
        e.second = d;
        edges[x-1].push_back(e);
    }
    int pre = 1;
    for (int i = 0; i < m; ++i) {
        int b, r;
        cin >> b >> r;
        if (track.empty()) {
            vex.push_back(getValue(1, r/100));
            track.push_back(b-1);
            pre = r/100;
        }
        else if (track[track.size()-1] == b-1){
            vex[vex.size() - 1] += getValue(pre, r/100);
            pre = r/100;
        }
        else {
            vex[vex.size() - 1] += getValue(1, pre);
            vex.push_back(getValue(1, r/100));
            track.push_back(b-1);
            pre = r/100;
        }
    }
    vex[vex.size() - 1] += getValue(1, pre);
    cout << func(n, edges, vex, track) << endl;
}