html5美食网站,html电影网页设计教程,哪个行业最需要推广,网站维护服务传送门——BZOJCH 传送门——Vjudge 设\(f_i\)表示\(i\)到\(1\)号点的最短距离#xff0c;\(g_i\)表示\(i\)到\(2\)号点的最短距离#xff0c;\(s_i\)表示\(n1\)号点到\(i\)号点的最短距离#xff0c;\(As_1,Bs_2\) 根据最短路三角形不等式#xff0c;\(|f_i - A| \leq s_i…传送门——BZOJCH 传送门——Vjudge 设\(f_i\)表示\(i\)到\(1\)号点的最短距离\(g_i\)表示\(i\)到\(2\)号点的最短距离\(s_i\)表示\(n1\)号点到\(i\)号点的最短距离\(As_1,Bs_2\) 根据最短路三角形不等式\(|f_i - A| \leq s_i \leq f_i A , |g_i - B| \leq s_i \leq g_i B\) 而\(s_i\)要取到最小值所以\(s_i \max\{|f_i - A| , |g_i - B|\}\) 所以我们要求的是\(\sum\limits_{i1}^N \max\{|f_i - A| , |g_i - B|\}\)这相当于求一个动点\((A,B)\)到平面上\(N\)个点\((f_i,g_i)\)的最小切比雪夫距离和。 切比雪夫距离可以转为曼哈顿距离将坐标\((x,y)\)变为\((\frac{xy}{2} , \frac{x-y}{2})\)前者的切比雪夫距离等效于后者的曼哈顿距离。而曼哈顿距离可以直接拆开横纵坐标然后取中位数。 注意我天真的以为2012年的题不会卡SPFA…… #includeiostream
#includecstdio
#includecstdlib
#includectime
#includealgorithm
#includecstring
#includeiomanip
#includequeue
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;inline int read(){int a 0;char c getchar();while(!isdigit(c) c ! EOF)c getchar();while(isdigit(c)){a a * 10 c - 48;c getchar();}return a;
}#define PLI pair long long , int
#define st first
#define nd second
const int MAXN 1e5 7;
struct Edge{int end , upEd , w;
}Ed[MAXN * 6];
int head[MAXN] , N , M , cntEd;
long long dis[2][MAXN];
priority_queue PLI q;inline void addEd(int a , int b , int w){Ed[cntEd].end b;Ed[cntEd].w w;Ed[cntEd].upEd head[a];head[a] cntEd;
}void SPFA(int ind){memset(dis[ind] , 0x3f , sizeof(long long) * (N 1));dis[ind][ind 1] 0;q.push(PLI(0 , ind 1));while(!q.empty()){PLI t q.top();q.pop();if(-t.st ! dis[ind][t.nd]) continue;for(int i head[t.nd] ; i ; i Ed[i].upEd)if(dis[ind][Ed[i].end] dis[ind][t.nd] Ed[i].w){dis[ind][Ed[i].end] dis[ind][t.nd] Ed[i].w;q.push(PLI(-dis[ind][Ed[i].end] , Ed[i].end));}}
}inline long long abss(long long x){return x 0 ? -x : x;}void out(long long a , int b){cout a / b .;a % b;for(int i 1 ; i 8 ; i){a * 10;cout a / b;a % b;}putchar(\n);
}int main(){vector long long x , y;for(int T read() ; T ; --T){N read(); M read();memset(head , 0 , sizeof(int) * (N 1));cntEd 0;for(int i 1 ; i M ; i){int a read() , b read() , c read();addEd(a , b , c); addEd(b , a , c);}SPFA(0); SPFA(1);x.clear(); y.clear();long long sum 0;for(int i 1 ; i N ; i){x.push_back(dis[0][i] - dis[1][i]);y.push_back(dis[0][i] dis[1][i]);}sort(x.begin() , x.end()); sort(y.begin() , y.end());long long mid x[N 1];for(int i 0 ; i N ; i)sum abss(x[i] - mid);mid y[N 1];for(int i 0 ; i N ; i)sum abss(y[i] - mid);out(sum , 2 * N);cerr N sum endl;}return 0;
} 转载于:https://www.cnblogs.com/Itst/p/10467947.html
