Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define xx first
- #define yy second
- #define LL long long
- #define inf 100000000
- #define pb push_back
- #define vsort(v) sort(v.begin(),v.end())
- #define pi acos(-1)
- #define clr(a,b) memset(a,b,sizeof a)
- #define bclr(a) memset(a,false,sizeof a)
- #define pii pair<int,int>
- #define MOD 1000000007
- #define MP make_pair
- #define MX 2000006
- using namespace std;
- vector<pii>road[2][1255];
- bool chk[2][1255][1255];
- priority_queue<pii>PQ;
- int dis[2][1255][1255];
- void solve(int s,int n,int f){
- for(int i=1;i<=n;i++){
- dis[f][s][i]=1000000000;
- }
- dis[f][s][s]=0;
- PQ.push(MP(0,s));
- while(!PQ.empty()){
- pii P=PQ.top();PQ.pop();
- int u=P.yy;
- if(chk[f][s][u]) continue;
- chk[f][s][u]=true;
- for(int i=0;i<road[f][u].size();i++){
- int v=road[f][u][i].xx,w=road[f][u][i].yy;
- if(dis[f][s][v]>dis[f][s][u]+w){
- dis[f][s][v]=dis[f][s][u]+w;
- PQ.push(MP(-dis[f][s][v],v));
- }
- }
- }
- while(!PQ.empty()) PQ.pop();
- }
- int main(){
- int n;
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- int c;
- scanf("%d",&c);
- road[0][i].pb(MP(j,c));
- }
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- int c;
- scanf("%d",&c);
- road[1][i].pb(MP(j,c));
- }
- }
- int u,v;
- scanf("%d%d",&u,&v);
- for(int i=1;i<=n;i++) solve(i,n,0);
- for(int i=1;i<=n;i++) solve(i,n,1);
- int res=1000000000;
- for(int i=1;i<=n;i++){
- if(i==u || i==v) continue;
- res=min(res,dis[0][u][i]+dis[1][i][v]);
- res=min(res,dis[1][u][i]+dis[0][i][v]);
- }
- cout<<res<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement