考察:最短路
思路:
很容易看出t就是一般最短路的权值,快速地打了一遍dijkstra板子结果发现输出结果和样例不一样,那么答案错在哪里呢?
我们调试一下就可以发现,到达中间某点的耗时晚,不一定到达终点就晚,因为到达时间由到达每个点的时间和速度决定.
之前说过最短路可以和dp联系起来,那么转化一下就是我们用到达的每个点的时间不足以计算出最短时间,所以需要增加一维状态,即速度.
最后标记一下每个状态由哪个状态转来即可.
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 using namespace std;
5 const int N = 160,M = N*N,INF = 0x3f3f3f3f,S = 510;
6 typedef pair<int,int> PII;
7 int n,m,e,idx,h[N];
8 PII pre[N][S];
9 double dist[N][S];
10 bool st[N][S];
11 struct Road{
12 int to,ne,v,L;
13 }road[M];
14 struct Node{
15 double t;
16 int u,vs;
17 bool operator>(const Node& s)const{
18 return this->t>s.t;
19 }
20 };
21 void add(int a,int b,int v,int l)
22 {
23 road[idx].to = b,road[idx].v = v,road[idx].L = l,road[idx].ne = h[a],h[a] = idx++;
24 }
25 void dijkstra(int s)
26 {
27 for(int i=1;i<=n;i++)
28 for(int j=0;j<=500;j++) dist[i][j] = INF;
29 dist[s][70] = 0;
30 priority_queue<Node,vector<Node>,greater<Node> > q;
31 q.push({0,s,70});
32 while(q.size())
33 {
34 Node it = q.top();
35 q.pop();
36 int u = it.u,speed = it.vs;
37 if(st[u][speed]) continue;
38 st[u][speed] = 1;
39 for(int i=h[u];~i;i=road[i].ne)
40 {
41 int v = road[i].to,L = road[i].L,limit = road[i].v;
42 int new_v = !limit?speed:limit;
43 double new_t = L*1.0/new_v;
44 if(dist[v][new_v]>dist[u][speed]+new_t)
45 {
46 dist[v][new_v] = dist[u][speed]+new_t;
47 pre[v][new_v] = {u,speed};
48 q.push({dist[v][new_v],v,new_v});
49 }
50 }
51 }
52 }
53 void dfs(int u,int v)
54 {
55 if(u==-1) return;
56 dfs(pre[u][v].first,pre[u][v].second);
57 printf("%d ",u);
58 }
59 int main()
60 {
61 scanf("%d%d%d",&n,&m,&e);
62 memset(h,-1,sizeof h);
63 memset(pre,-1,sizeof pre);
64 while(m--)
65 {
66 int a,b,v,l;
67 scanf("%d%d%d%d",&a,&b,&v,&l);
68 add(a,b,v,l);
69 }
70 dijkstra(0);
71 double minv = INF;int tar_v;
72 for(int i=0;i<=500;i++)
73 if(dist[e][i]<minv)
74 {
75 tar_v = i;
76 minv = dist[e][i];
77 }
78 dfs(e,tar_v);
79 printf("\n");
80 return 0;
81 }