L - Subway(最短路spfa)
Sample Input
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
Sample Output
21
思路
- 这一题难在输入和建图，，，，，
- 对于建图，我说一些需要注意的地方：
1.首先 起点要与所有的火车站 建了一条边（起点 -> 火车站）权值为人走过这段距离所用的时间
2.汽车 所有的火车站与终点 建了一条边 （火车站-> 终点）权值为人走过这段距离所用的时间
3. 这题一条最需要注意： 在任意一组 车站点之间，相邻的 站点之间 要建立双向边（权值为：火车的行走的时间）
4. 所有火车站之间应该 也应该建了 双向边，这个边的权值（时间），一定是人走过两个车站的时间
题解一
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define Pir pair<double, double>
const int maxm = 100005;
struct Pos
{
double x,y;
} pos[maxm];
int k = 2;
double Dis(Pos a, Pos b)
{
return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) );
}
struct Edge
{
int v;
double w;
int next;
} edge[maxm];
int head[maxm];
double dis[maxm];
int cnt = 0;
void Add(int u, int v, double w)
{
edge[++ cnt] = (Edge){ v, w, head[u]}; head[u] = cnt;
}
double Spfa(int s, int e)
{
int use[maxm];
for(int i = 0; i <= k; i ++)
dis[i] = INF, use[i] = 0;
dis[s] = 0;
queue<int> q;
q.push(s);
int u,v;
double w;
while(! q.empty())
{
u = q.front(); q.pop();
use[u] = 0;
for(int i = head[u]; i; i = edge[i].next)
{
v = edge[i].v;
w = edge[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(! use[v])
{
q.push(v);
use[v] = 1;
}
}
}
}
return dis[e];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
//freopen("T.txt","r",stdin);
cin >> pos[0].x >> pos[0].y >> pos[1].x >> pos[1].y;
double x,y;
while(cin >> x >> y)
{
pos[k].x = x; pos[k ++].y = y;
while(cin >> x >> y && (x!=-1 && y!=-1))
{
pos[k].x = x; pos[k].y = y;
Add(k - 1, k, Dis(pos[k-1], pos[k])/2000*3);
Add(k, k - 1, Dis(pos[k], pos[k-1])/2000*3);
k ++;
}
}
for(int i = 0; i < 2; i ++)
{
for(int j = 2; j < k-1; j ++)
{
if(i == 0)
Add(i, j, Dis(pos[i], pos[j])/500*3);
if(i == 1)
Add(j, i, Dis(pos[i], pos[j])/500*3);
}
}
for(int i = 0; i < k; i ++)
for(int j = i + 1; j < k; j ++)
{
Add(i, j, Dis(pos[i], pos[j])/500*3);
Add(j, i, Dis(pos[i], pos[j])/500*3);
}
Add(0, 1, Dis(pos[0], pos[1])/500*3);
cout << int( Spfa(0, 1) + 0.5) << endl;
return 0;
}
题解二（别人的）
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<cstdio>
#include<queue>
#include<stack>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 205;
const double wsp = 10 * 1000 / 60;
const double ssp = 40 * 1000 / 60;
struct Node{
double x, y;
}node[MAXN];
struct ff{
int x, d;
ff(){}
ff( int a, double b ){ x = a; d = b; }
bool operator <( const ff & a )const{
return d > a.d;
}
};
int cnt;
double cost[MAXN][MAXN];
double dis[MAXN];
double gdis( int pre, int pos ){
double dx = node[pre].x - node[pos].x;
double dy = node[pre].y - node[pos].y;
return sqrt( dx * dx + dy * dy );
}
void dij(){
for( int i = 1; i < MAXN; i++ )
dis[i] = INF;
dis[1] = 0;
priority_queue<ff> Q;
Q.push( ff( 1, dis[1]) );
while( !Q.empty() ){
ff temp = Q.top(); Q.pop();
int x = temp.x;
if( temp.d > dis[x] ) continue;
for( int i = 1; i < cnt; i++ ){
if( dis[i] > dis[x] + cost[x][i] ){
dis[i] = dis[x] + cost[x][i];
Q.push( ff( i, dis[i] ) );
}
}
}
}
int main(){
ios::sync_with_stdio( false );
for( int i = 0; i < MAXN; i++ )
for( int j = 0; j < MAXN; j++ )
cost[i][j] = INF;
cin >> node[1].x >> node[1].y >> node[2].x >> node[2].y;
cnt = 3;
while( cin >> node[cnt].x >> node[cnt].y ){
cnt++;
while( cin >> node[cnt].x >> node[cnt].y, !( node[cnt].x == -1 && node[cnt].y == -1 ) ){
cost[cnt][cnt - 1] = cost[cnt - 1][cnt] = gdis( cnt - 1, cnt ) / ssp;
cnt++;
}
}
for( int i = 1; i < cnt - 1; i++ ){
cost[i][i] = 0;
for( int j = i + 1; j < cnt; j++ ){
cost[i][j] = cost[j][i] = min( cost[i][j], gdis( i, j ) / wsp );
}
}
dij();
cout << int( dis[2] + 0.5 );
return 0;
}