A - Til the Cows Come Home
最短路模板，从终点到起点，双向建边
/***********************************************
* Author: fisty
* Created Time: 2015/1/28 20:55:21
* File Name : 4_A.cpp
*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define MAX_N 2000
int T, N;
struct node{
int to;
int cost;
node(int _to, int _cost) : to(_to), cost(_cost){}
};
vector<node> G[MAX_N];
int d[MAX_N];
int dijsktra(){
d[N] = 0;
priority_queue<P , vector<P>, greater<P> > que;
que.push(P(d[N], N));
while(que.size()){
P q = que.top(); que.pop();
int v = q.second;
if(d[v] < q.first) continue;
for(int i = 0;i < G[v].size(); i++){
node &e = G[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
return d[1];
}
int main() {
//freopen("in.txt", "r", stdin);
cin.tie(0);
ios::sync_with_stdio(false);
cin >> T >> N;
memset(d, 0x3f, sizeof(d));
for(int i = 0;i < T; i++){
//构图
int u, v, cost;
cin >> u >> v >> cost;
G[u].push_back(node(v, cost));
G[v].push_back(node(u, cost));
}
int ans = dijsktra();
cout << ans << endl;
return 0;
}
B -Frogger
题目大意:
给出两只青蛙的坐标A、B，和其他的n-2个坐标，任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路，每一条通路的元素都是这条通路中前后两个点的距离，这些距离中又有一个最大距离。
现在要求求出所有通路的最大距离，并把这些最大距离作比较，把最小的一个最大距离作为青蛙的最小跳远距离。
Floyd算法
用Floyd算法求出两两最短路，再求出从每个点开始的最长路，最后从这n个最长路中求出最小的那个即为所求。
/***********************************************
* Author: fisty
* Created Time: 2015/1/29 10:55:02
* File Name : 4_B.cpp
*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
typedef long long LL;
typedef pair<double, int> PII;
#define MAX_N 210
int N;
double G[MAX_N][MAX_N];
struct Point{
double x, y;
}P[MAX_N];
double solve(){
for(int k = 0;k < N; k++){
for(int i = 0;i < N-1; i++){
for(int j = i+1; j < N; j++){
if(G[i][k] < G[i][j] && G[k][j] < G[i][j]){
G[j][i] = G[i][j] = max(G[i][k], G[k][j]);
}
}
}
}
return G[0][1];
}
int main() {
//freopen("in.txt", "r", stdin);
//cin.tie(0);
//ios::sync_with_stdio(false);
int cnt = 1;
while(~scanf("%d", &N)){
if(!N) break;
printf("Scenario #%d\n", cnt++);
for(int i = 0;i < N; i++){
scanf("%lf%lf", &P[i].x, &P[i].y);
}
for(int i = 0;i < N-1; i++){
for(int j = i+1; j < N; j++){
double x = P[i].x - P[j].x;
double y = P[i].y - P[j].y;
double cost = sqrt(x*x + y*y);
G[i][j] = G[j][i] = cost;
}
}
double ans = solve();
printf("Frog Distance = %.3f\n\n", ans);
}
return 0;
}
C - Heavy Transportation
和上个题要求的正好相反,求最短路径的一条边最小承载量，这里出发点要特殊处理，因为d[s] = 0；之后的点只要d[v] < d[u] && d[v] < cost就可用d[v] = min(d[u], cost)来推了，用的dijsktra,Floyd会超时
/***********************************************
* Author: fisty
* Created Time: 2015/1/30 11:03:39
* File Name : 4_C.cpp
*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
typedef long long LL;
typedef pair<int, int> P;
#define MAX_N 1010
int N, M;
struct edge{
int to;
int cost;
edge(int _to ,int _cost) :to(_to), cost(_cost){}
};
vector<edge> G[MAX_N];
int d[MAX_N];
int vis[MAX_N];
int solve(){
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));
d[1] = 0;
priority_queue <int> que;
for(int i = 0; i < G[1].size(); i++){
//先处理起点，因为与后面不一样
edge e = G[1][i];
d[e.to] = e.cost;
que.push(e.to);
}
//dijsktra
while(que.size()){
int v = que.top(); que.pop();
for(int i = 0;i < G[v].size(); i++){
edge e = G[v][i];
if(d[e.to] < min(d[v], e.cost)){
//同时小于边和上一个顶点时，才能更新
d[e.to] = min(d[v], e.cost);
que.push(e.to);
}
}
}
return d[N];
}
int main() {
//freopen("in.txt", "r", stdin);
//cin.tie(0);
//ios::sync_with_stdio(false);
int cnt = 1;
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &N, &M);
printf("Scenario #%d:\n", cnt++);
memset(G, 0, sizeof(G));
for(int i = 0;i < M; i++){
int a, b, cost;
scanf("%d%d%d", &a, &b, &cost);
G[a].push_back(edge(b, cost));
G[b].push_back(edge(a, cost));
}
int ans = solve();
printf("%d\n\n", ans);
}
return 0;
}
<span style="font-size:24px;color:#FF0000;">
</span>
D -
Silver Cow Party
1.求i( 1<= i <=n)到X的最短路径，保存在d_1[i]
2.求X到所有i(1 <= i <= n)的最短路，保存在d_2[i]
3求一条最长的最短路 ans = max(ans, d_1[i] + d_2[i]) (1 <= i <= n)
/***********************************************
* Author: fisty
* Created Time: 2015/1/30 17:51:30
* File Name : 4_D.cpp
*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define MAX_N 1100
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
struct edge{
int to;
int cost;
edge(int _to, int _cost) : to(_to), cost(_cost){}
};
vector<edge> G[MAX_N];
int n, M ,X;
int d[MAX_N];
int d_1[MAX_N], d_2[MAX_N]; //去和回
int solve(){
//memset(d_1, 0, sizeof(d_1));
//memset(d_2, 0, sizeof(d_2));
for(int i = 1;i <= n; i++){
int s = i; //出发点
//从各个地方出发到X
if(i == X) continue;
priority_queue<P, vector<P>, greater<P> > que;
memset(d, 0x3f, sizeof(d));
d[s] = 0;
que.push(P(d[s], s));
while(que.size()){
P q = que.top(); que.pop();
int v = q.second;
if(d[v] < q.first) continue;
for(int j = 0;j < G[v].size(); j++){
edge e = G[v][j];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
d_1[i] = d[X];
//Debug(d[X]);
}
//从X出发到各地
priority_queue<P, vector<P>, greater<P> > que;
memset(d, 0x3f, sizeof(d));
d[X] = 0;
que.push(P(d[X], X));
while(que.size()){
P q = que.top(); que.pop();
int v = q.second;
if(d[v] < q.first) continue;
for(int i = 0;i < G[v].size(); i++){
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
for(int i = 1; i <= n; i++){
if(i == X) continue;
d_2[i] = d[i];
//Debug(d[i]);
}
//求一条最长的最短路
int ans = -INF;
for(int i = 1; i <= n; i++){
if(i == X) continue;
ans = max(ans, d_1[i] + d_2[i]);
}
return ans;
}
int main(){
//freopen("in.txt", "r", stdin);
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> M >> X;
for(int i = 0;i < M; i++){
int a, b, cost;
cin >> a >> b >> cost;
//单向
G[a].push_back(edge(b, cost));
}
int ans = solve();
cout << ans << endl;
return 0;
}
E - Currency Exchange
题目大意有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币交换B币时，A到B的汇率是29.75，手续费
是0.39，那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加
货币的交换是可以重复多次的，所以我们需要找出是否存在正权回路，且最后得到的s金额是增加的
怎么找正权回路呢？（正权回路：在这一回路上，顶点的权值能不断增加即能一直进行松弛）