题意：n个电梯，100层楼，告诉每个电梯的速度和每个电梯会停的楼层数，起点在0层，终点是第k层，另外每次换乘需要等待60秒，问从0到k的最短时间是多少。
思路：这题就是读入比较蛋疼，然后根据输入建完图后跑一下Dijkstra。在更新时加入60秒。
代码：
?
#include #include #include #include #include #include #include #include #include #include #include #pragma comment (linker,/STACK:102400000,102400000) #define pi acos(-1.0) #define eps 1e-6 #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define FRE(i,a,b) for(i = a; i <= b; i++) #define FREE(i,a,b) for(i = a; i >= b; i--) #define FRL(i,a,b) for(i = a; i < b; i++) #define FRLL(i,a,b) for(i = a; i > b; i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define sf(n) scanf(%d, &n) #define sff(a,b) scanf(%d %d, &a, &b) #define sfff(a,b,c) scanf(%d %d %d, &a, &b, &c) #define pf printf #define DBG pf(Hi ) typedef long long ll; using namespace std; #define INF 0x3f3f3f3f #define mod 1000000009 const int maxn = 105; const int MAXN = 3005; const int MAXM = 200010; const int N = 1005; int mp[maxn][maxn],TIME[6]; int dist[maxn]; bool vis[maxn]; int n,k; char str[MAXN]; int a[maxn]; int readLine(char *s) { int L; for (L=0;(s[L]=getchar())!=' '&&s[L]!=EOF;L++) ; s[L]=0; return L; } void Dijkstra() { int i,j,now,mi; mem(dist,INF); mem(vis,false); for (i=0;i<100;i++) dist[i]=mp[0][i]; dist[0]=0; vis[0]=true; for (i=0;i<100;i++) { now=-1; mi=INF; for (j=0;j<100;j++) { if (!vis[j]&&mi>dist[j]) { now=j; mi=dist[j]; } } // printf(now=%d ,now); if (now==-1) break; // DBG; vis[now]=true; for (j=0;j<100;j++) { if (!vis[j]&&dist[j]>dist[now]+mp[now][j]+60) dist[j]=dist[now]+mp[now][j]+60; } } // for (i=0;i<=30;i++) // pf(%d ,dist[i]); if (dist[k]>=INF) pf(IMPOSSIBLE ); else pf(%d ,dist[k]); } int main() { #ifndef ONLINE_JUDGE freopen(C:/Users/lyf/Desktop/IN.txt,r,stdin); #endif int i,j; while (~sff(n,k)) { mem(mp,INF); for (i=0;i ? ?