题意:列车上行驶40, 其余走路速度10.问从家到学校的最短时间

分析:关键是建图:相邻站点的速度是40,否则都可以走路10的速度.读入数据也很变态.

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N = 2e2 + 5;const int E = N * N;const double INF = 1e30;struct Point	{	double x, y;}p[N];bool vis[N];double d[N];double w[N][N];double sx, sy, ex, ey;int tot;void Dijkstra(int s)	{	memset (vis, false, sizeof (vis));	for (int i=1; i<=tot; ++i)	{		d[i] = INF;	}	d[s] = 0;	for (int i=1; i<=tot; ++i)	{		double mn = INF;	int x = -1;		for (int j=1; j<=tot; ++j)	{			if (!vis[j] && mn > d[j])	mn = d[x=j];		}		if (x == -1)	break;		vis[x] = true;		for (int j=1; j<=tot; ++j)	{			if (!vis[j] && d[j] > d[x] + w[x][j])	{				d[j] = d[x] + w[x][j];			}		}	}}double squ(double x)	{	return x * x;}double get_cost(Point p1, Point p2, int v)	{	double dis = sqrt (squ (p1.x - p2.x) + squ (p1.y - p2.y)) / 1000;	return dis / v;}int main(void)	{	while (scanf ("%lf%lf%lf%lf", &sx, &sy, &ex, &ey) == 4)	{		for (int i=1; i
          
            tim) { w[i][i+1] = w[i+1][i] = tim; } } l = tot + 1; continue; } p[++tot].x = x; p[tot].y = y; } p[++tot].x = ex; p[tot].y = ey; for (int i=1; i
           
             tim) { w[i][j] = w[j][i] = tim; } } } Dijkstra (1); printf ("%.0f\n", d[tot] * 60); } return 0;}