hdoj 5636 Shortest Path

本文主要是介绍hdoj 5636 Shortest Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

        如果不考虑6个特殊点，两点间距离就是下标差。但是这6个点的存在有可能缩短了两点间距离，所以跑一下6个点到所有点的最短路(6*6*n的floyd)，对于每个询问，算一下直接s-t和s-6个点中的某个-t的最小值即可。

#include <iostream>  
#include <stdio.h>  
#include <cmath>  
#include <algorithm>  
#include <string>  
#include <memory.h>  
#include <vector>  
#include <queue>  
#include <stack> using namespace std;#define ll long longint dis[6][100010];int a[6];void ckMin(int &a,int b){if(b<a){a=b;}
}void ckMin(ll &a,ll b){if(b<a){a=b;}
}const ll mod = 1e9+7;int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=0;i<6;i++){cin>>a[i];for(int j=1;j<=n;j++){dis[i][j] = j-a[i];if(dis[i][j]<0){dis[i][j] = -dis[i][j];}}}ckMin(dis[0][a[1]],1);ckMin(dis[1][a[0]],1);ckMin(dis[2][a[3]],1);ckMin(dis[3][a[2]],1);ckMin(dis[4][a[5]],1);ckMin(dis[5][a[4]],1);for(int k=0;k<6;k++){for(int i=0;i<6;i++){for(int j=1;j<=n;j++){ckMin(dis[i][j],dis[i][a[k]]+dis[k][j]);}}}ll ans = 0;for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);ll tmp=abs(u-v);for(int j=0;j<6;j++){ckMin(tmp,abs(u-a[j])+dis[j][v]);}ans += tmp*i;ans%=mod;}cout<<ans<<endl;}return 0;
}

这篇关于hdoj 5636 Shortest Path的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---