1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;

const int MAXI = 5e6 + 7;
vector <pair <int, int> > graf[MAXI];
vector <pair <int, int> > graf1[MAXI];
bool odw[MAXI];
bool odw1[MAXI];
long long  odl[MAXI];
long long  odl1[MAXI];
const int MAXN = 2e3 + 7;
bool tab[MAXN][MAXN];

void dijkstra(){
    odl[1] = 0;
    priority_queue<pair<long long, int> > q;
    q.push(make_pair(0, 1));
    while(q.size()){
        int w = q.top().second;
        q.pop();
        if(odw[w]){
            continue;
        }
        odw[w] = true;
        for(int i = 0; i < graf[w].size(); i++){
            if(odl[graf[w][i].first] > odl[w] + graf[w][i].second){
                odl[graf[w][i].first] = odl[w] + graf[w][i].second;
                q.push(make_pair(-odl[graf[w][i].first], graf[w][i].first));
            }
        }
    }
}

void dijkstra1(){
    odl1[1] = 0;
    priority_queue<pair<long long, int> > q;
    q.push(make_pair(0, 1));
    while(q.size()){
        int w = q.top().second;
        q.pop();
        if(odw1[w]){
            continue;
        }
        odw1[w] = true;
        for(int i = 0; i < graf1[w].size(); i++){
            if(odl1[graf1[w][i].first] > odl1[w] + graf1[w][i].second){
                odl1[graf1[w][i].first] = odl1[w] + graf1[w][i].second;
                q.push(make_pair(-odl[graf1[w][i].first], graf1[w][i].first));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k, n, m; 
    long long a, b, ilepie, iledru;
    long long mini = 1000000000000000007;
    cin >> n >> m >> k;
    char wczyt;
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= m; j++){
            cin >> wczyt;
            if(wczyt == 'X'){
                tab[i][j] = 1;
            }
            else{
                tab[i][j] = 0;
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= m; j++){
            if(tab[i][j] == 0){
                if(i != n - 1 && tab[i + 1][j] == 0){
                    graf[i * m + j].push_back(make_pair((i + 1) * m + j, 1));
                }
                if(j != m && tab[i][j + 1] == 0){
                    graf[i * m + j].push_back(make_pair(i * m + j + 1, 1));
                }
                if(i != 0 && tab[i - 1][j] == 0){
                    graf[i * m + j].push_back(make_pair((i - 1) * m + j, 1000000));
                }
                if(j != 1 && tab[i][j - 1] == 0){
                    graf[i * m + j].push_back(make_pair(i * m + j - 1, 1000000));
                }
                if(i != n - 1 && tab[i + 1][j] == 0){
                    graf1[i * m + j].push_back(make_pair((i + 1) * m + j, 1000000));
                }
                if(j != m && tab[i][j + 1] == 0){
                    graf1[i * m + j].push_back(make_pair(i * m + j + 1, 1000000));
                }
                if(i != 0 && tab[i - 1][j] == 0){
                    graf1[i * m + j].push_back(make_pair((i - 1) * m + j, 1));
                }
                if(j != 1 && tab[i][j - 1] == 0){
                    graf1[i * m + j].push_back(make_pair(i * m + j - 1, 1));
                }
            }
            odl[i * m + j] = 1000000007;
            odl1[i * m + j] = 1000000007;
        }
    }
    dijkstra();
    dijkstra1();
    ilepie = odl[(n - 1) * m + m] / 1000000;
    iledru = odl[(n - 1) * m + m] - ilepie * 1000000;
    long long ilepie1 = odl1[(n - 1) * m + m] / 1000000;
    long long iledru1 = odl1[(n - 1) * m + m] - ilepie1 * 1000000;
    for(int i = 1; i <= k; i++){
        cin >> a >> b;
        if(a <= b){
            odl[i] = a * iledru + b * ilepie;
            mini = min(mini, a * iledru + b * ilepie);
            odl[i] = b * iledru1 + a * ilepie1;
            mini = min(mini, b * iledru1 + a * ilepie1);
        }
        else{
            odl[i] = b * iledru1 + a * ilepie1;
            mini = min(mini, b * iledru1 + a * ilepie1);
            odl[i] = b * iledru1 + a * ilepie1;
            mini = min(mini, b * iledru1 + a * ilepie1);
        }
    }
    a = 0;
    for(int i = 1; i <= k; i++){
        if(odl[i] == mini){
            a++;
        }
    }
    cout << mini << " " << a;
    return 0;
}