Advertisement
Guest User

Untitled

a guest
Oct 4th, 2015
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define xx first
  4. #define yy second
  5. #define LL long long
  6. #define inf 100000000
  7. #define pb push_back
  8. #define vsort(v) sort(v.begin(),v.end())
  9. #define pi acos(-1)
  10. #define clr(a,b) memset(a,b,sizeof a)
  11. #define bclr(a) memset(a,false,sizeof a)
  12. #define pii pair<int,int>
  13. #define MOD 1000000007
  14. #define MP make_pair
  15. #define MX 2000006
  16.  
  17. using namespace std;
  18. vector<pii>road[2][1255];
  19. bool chk[2][1255][1255];
  20. priority_queue<pii>PQ;
  21. int dis[2][1255][1255];
  22.  
  23. void solve(int s,int n,int f){
  24.     for(int i=1;i<=n;i++){
  25.         dis[f][s][i]=1000000000;
  26.     }
  27.     dis[f][s][s]=0;
  28.     PQ.push(MP(0,s));
  29.     while(!PQ.empty()){
  30.         pii P=PQ.top();PQ.pop();
  31.         int u=P.yy;
  32.         if(chk[f][s][u]) continue;
  33.         chk[f][s][u]=true;
  34.         for(int i=0;i<road[f][u].size();i++){
  35.             int v=road[f][u][i].xx,w=road[f][u][i].yy;
  36.             if(dis[f][s][v]>dis[f][s][u]+w){
  37.                 dis[f][s][v]=dis[f][s][u]+w;
  38.                 PQ.push(MP(-dis[f][s][v],v));
  39.             }
  40.         }
  41.     }
  42.     while(!PQ.empty()) PQ.pop();
  43. }
  44.  
  45. int main(){
  46.     int n;
  47.     scanf("%d",&n);
  48.     for(int i=1;i<=n;i++){
  49.         for(int j=1;j<=n;j++){
  50.             int c;
  51.             scanf("%d",&c);
  52.             road[0][i].pb(MP(j,c));
  53.         }
  54.     }
  55.     for(int i=1;i<=n;i++){
  56.         for(int j=1;j<=n;j++){
  57.             int c;
  58.             scanf("%d",&c);
  59.             road[1][i].pb(MP(j,c));
  60.         }
  61.     }
  62.     int u,v;
  63.     scanf("%d%d",&u,&v);
  64.     for(int i=1;i<=n;i++) solve(i,n,0);
  65.     for(int i=1;i<=n;i++) solve(i,n,1);
  66.  
  67.     int res=1000000000;
  68.     for(int i=1;i<=n;i++){
  69.         if(i==u || i==v) continue;
  70.         res=min(res,dis[0][u][i]+dis[1][i][v]);
  71.         res=min(res,dis[1][u][i]+dis[0][i][v]);
  72.     }
  73.     cout<<res<<endl;
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement