POJ subway 600K 0MS
题意：乘坐地铁从家到学校，地铁40km/h 步行10km/h , 已知各个站点的x，y坐标，输入的信息每个列次用-，-1隔开，要求花费的时间最少
解决方案：把家和学校各看成一个站点，求出相邻站点的权值（路程/速度），以站点数量建立map，保留两站之间的距离，然后dijsktra算法寻找两站点间最短路径
问题：结束条件EOF，sign初始值
#include<iostream>
#include<cmath>
#define MAX 10000000.0
using namespace std;
double pt[][];// 存放站点的坐标值
double map[][];// 存放各个站点直接的权值（路程/速度）
double d[]; //记录各点到起点最短距离
double dijkstra(int x, int y,int n)// pt[x]为起点 ,pt[y]为终点 一共n个站点
{
int i,j,k,tx=x,next;//next下一个最短路径位置
double min ;
bool visited[];
memset(visited,false,sizeof(visited));
visited[x]=true;
for (i=;i<n;i++)
if(!visited[i])d[i]=map[][i];
for(i=; i<n; i++)
{
min = MAX;
for (j=; j<n; j++)//找到附近最小的路径
if(!visited[j] && d[j]<min)
min=d[j], next=j;
visited[next]= true;//访问
if(next==y) break; //找到终点的最短距离，结束
for (j=; j<n; j++)//更新各点到源点最短路信息
if(!visited[j] && d[j]>d[next]+map[next][j])
d[j]=d[next]+map[next][j];
}
return d[y];
}
int main()
{
char c;
int i,j,k,num,sign;//num记录站点个数， sign标记站点关联
cin >> pt[][] >> pt[][] >> pt[][] >> pt[][];//pt[0],pt[1] 记录起点、终点 memset(map,,sizeof(map));
num = ,sign = ;//sign=0 隔离站点关联
while( scanf("%lf%lf",&pt[num][],&pt[num][])!=EOF)
{
// c=getchar();if(c=='#') break;
if(pt[num][]==- && pt[num][]==-)
{
sign = ; continue;
}
if(sign)//求出相邻地铁站点间的权值
map[num][num-]=map[num-][num]=
(sqrt(pow(pt[num][]-pt[num-][],2.0)+pow(pt[num][]-pt[num-][],2.0)))/40000.0;
++num, sign =;
}
//求出剩余各个站点间的权值
for(i=; i<num; i++)
for (j=; j<num; j++)
if(map[i][j]==) map[i][j]=map[j][i]=(sqrt((pt[i][]-pt[j][])*(pt[i][]-pt[j][])+(pt[i][]-pt[j][])*(pt[i][]-pt[j][])))/10000.0;
printf("%0.lf\n",dijkstra(,,num)*);//四舍五入输出结果
return ;
}
这是第一次做图论题，复习了一下Dijsktra算法，关键是建立map模型。。。