比較簡單的最短路問題,唯一的不同是更換電梯的時候需要多加60s等待時間,而且第一次上電梯不需要等待60s 。注意到這些細節之後在結構體中多保存一個電梯的id,這樣在松弛操作的時候分情況討論一下就行了 。
細節參見代碼:
#includeusing namespace std; const double INF = 1000000000; const int maxn = 505; int n,k,done[maxn],kase = 0,cur,t[maxn],a[maxn]; int d[maxn]; char s[maxn]; struct Node { int from,to,d,id; Node(int from=0,int to=0,int d=0,int id=0):from(from),to(to),d(d),id(id) {} }e[maxn*maxn] ; vector g[maxn]; struct heapNode{ int d,u,id; bool operator < (const heapNode& rhs) const { return d > rhs.d; } }; int dijkstra(int s) { priority_queue q; for(int i=0;i<100;i++) d[i] = INF , done[i] = 0; d[s] = 0; q.push((heapNode){0,s,-1}); while(!q.empty()) { heapNode x = q.top(); q.pop(); int u = x.u; if(u == k) return d[u]; if(done[u]) continue; done[u] = true; for(int i=0;i d[u] + ed.d + 60) { d[ed.to] = d[u] + ed.d + 60; q.push((heapNode){d[ed.to],ed.to,ed.id}); } else { if(d[ed.to] > d[u] + ed.d) { d[ed.to] = d[u] + ed.d; q.push((heapNode){d[ed.to],ed.to,ed.id}); } } } } return -1; } int main() { while(~scanf(%d%d,&n,&k)) { for(int i=0;i