/*
ID: himuhas1
TASK: cowtour
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl
using namespace std;
#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
ASDF& operator,(int &a) {
sf("%d", &a);
return *this;
}
ASDF& operator,(long int &a){
sf("%ld", &a);
return *this;
}
ASDF& operator,(long long int &a){
sf("%lld", &a);
return *this;
}
ASDF& operator,(char &c){
sf("%c", &c);
return *this;
}
ASDF& operator,(double &d){
sf("%lf", &d);
return *this;
}
template<typename T>
ASDF& operator,(T &a){
cin>>a;
return *this;
}
}asdf;
struct ASDFG{
template<typename T>
ASDFG& operator,(vector<T> &v){
pf("[");
cout<<v[0];
FOR(i, 1, SZ(v)){
cout<<", "<<v[i];
}
pf("]");
return *this;
}
template<typename T>
ASDFG& operator,(T x) {
cout<<x<<" ";
return *this;
}
}asdfg;
//Header ends here
int n;
#define MAXX 151
#define INF 1e10
double dist[MAXX][MAXX];
char graph[MAXX][MAXX];
paii points[MAXX];
int parent[MAXX];
double maxDistFrom[MAXX];
template<typename T>
T sqr(T a)
{
return a*a;
}
double calculateDist(paii a, paii b)
{
return sqrt( sqr(a.fr - b.fr) + sqr(a.sc - b.sc) );
}
int find(int u)
{
if(parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
int main()
{
#ifndef hasibpc
read("cowtour.in");
write("cowtour.out");
#endif // hasibpc
take(n);
int p, q;
dd minDist = INF;
//debug(minDist);
loop(i, n)
{
take(points[i].fr, points[i].sc);
parent[i] = i;
}
loop(i, n)
{
sf("%s", graph[i] );
loop(j, n)
{
if(graph[i][j] == '1')
{
dist[i][j] = calculateDist(points[i], points[j]);
parent[find(i)] = find(j);
}
else
{
dist[i][j] = INF;
}
}
}
loop(k, n)
loop(i, n)
loop(j, n)
if(dist[i][j] > dist[i][k] + dist[k][j])
dist[i][j] = dist[i][k] + dist[k][j];
map<int, double>mp;
loop(i, n)
{
FOR(j, i+1, n)
{
if(find(i) == find(j))
{
maxDistFrom[i] = max(maxDistFrom[i], dist[i][j]);
maxDistFrom[j] = max(maxDistFrom[j], dist[j][i]);
}
}
double &ret = mp[find(i)];
ret = max(ret, maxDistFrom[i]);
}
loop(i, n)
{
FOR(j, i+1, n)
{
if(find(i) != find(j))
{
minDist = min(minDist, max(max(calculateDist(points[i], points[j]) + maxDistFrom[i] + maxDistFrom[j],mp[find(i)]), mp[find(j)]) );
}
}
}
pf("%.6lf\n", minDist);
return 0;
}
Category Archives: Floyd-Warshall
(UVa) 10246 – Asterix and Obelix
0
/*
user: php
link: uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1187
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<string>
#include<sstream>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define get2int(a, b) getint(a), getint(b)
#define get3int(a, b, c) getint(a), get2int(b, c)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define pi acos(-1.0)
#define INF 1<<29
#define ll long long
#define dd double
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define MP make_pair
#define pb push_back
#define fr first
#define sc second
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define all(v) v.begin(), v.end()
#define mod abs
using namespace std;
#define MAXX 82
int C, R, Q;
int dist[MAXX][MAXX];
int festcost[MAXX][MAXX];
int main()
{
//read;
int kaseno = 0;
int p, q, d;
while(1)
{
get3int(C, R, Q);
if(C+R+Q == 0) break;
loop(i, C)
{
loop(j, C)
{
if(i == j) dist[i][j] = 0;
else dist[i][j] = festcost[i][j] = INF;
}
}
loop(i, C)
{
getint(d);
festcost[i][i] = d;
}
loop(i, R)
{
get3int(p, q, d);
p--; q--;
dist[p][q] = dist[q][p] = d;
festcost[p][q] = festcost[q][p] = max(festcost[p][p], festcost[q][q]);
}
loop(k, C)
{
loop(i, C)
{
loop(j, C)
{
if(dist[i][j] + festcost[i][j] > dist[i][k] + dist[k][j] + max(festcost[i][k], festcost[k][j]))
{
dist[i][j] = dist[i][k] + dist[k][j];
festcost[i][j] = max(festcost[i][k], festcost[k][j]);
}
}
}
}
///////test
loop(k, C)
{
loop(i, C)
{
loop(j, C)
{
if(dist[i][j] + festcost[i][j] > dist[i][k] + dist[k][j] + max(festcost[i][k], festcost[k][j]))
{
dist[i][j] = dist[i][k] + dist[k][j];
festcost[i][j] = max(festcost[i][k], festcost[k][j]);
}
}
}
}
///////
if(kaseno) pf("\n");
pf("Case #%d\n", ++kaseno);
loop(i, Q)
{
get2int(p, q);
p--; q--;
if(dist[p][q] + festcost[p][q] >= INF)
puts("-1");
else pf("%d\n", dist[p][q] + festcost[p][q]);
}
}
return 0;
}
(UVa) 11463 – Commandos
0
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2458
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<sstream>
#include<utility>
#include <cstdarg>
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define getint(n) sf("%d", &n)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define SZ(a) int(a.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define dd double
#define paii pair<int, int>
#define pall pair<ll, ll>
#define MP make_pair
#define fr first
#define sc second
#define mod abs
#define pf printf
#define sf scanf
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define INF 100000
using namespace std;
#define MAXX 101
int dist[MAXX][MAXX];
int cntBuildings, cntRoads;
int main()
{
int kases, kaseno = 0;
getint(kases);
int p, q;
int result;
while(kases--)
{
getint(cntBuildings); getint(cntRoads);
loop(i, cntBuildings)
{
loop(j, cntBuildings)
{
if(i == j) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
while(cntRoads--)
{
getint(p); getint(q);
dist[p][q] = dist[q][p] = 1;
}
getint(p); getint(q);
loop(k, cntBuildings) loop(i, cntBuildings) loop(j, cntBuildings) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j] );
result = -1;
loop(i, cntBuildings)
{
result = max(result, dist[p][i] + dist[i][q] );
}
pf("Case %d: %d\n", ++kaseno, result);
}
}
UnLucky Codes 