题目大意
葫芦世界有n个葫芦，标号为1~ n。n个葫芦由m条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在1号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到n号葫芦上，其中每个葫芦只经过一次。
小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。
题目分析
又是求比值，按照分数规划套路可以二分答案。
二分答案$x$，每次将每一条边的权值减去$x$求最短路，判断 $1\rightarrow n$的最短路是否大于$0$。若大于$0$，则说明答案$ans\gt x$，否则说明$ans \lt x$。
然后就可以二分了。
当然因为这道题数据范围比较小，我们也可以建立分层图。
实现方式就是Spfa开两维。
$dist[i,j]$表示到达$i$结点，经过$j$条边的最短路径。
代码
本人写的分层图1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=205;
struct Edge {
int from,to,dist;
};
vector<Edge>edges[maxn];
int n,m,inque[maxn][maxn];
double dist[maxn][maxn],ans=1e17;
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {
x,y,v
});
}
struct QueNode {
int u,d;
};
void Spfa(int s) {
queue<QueNode>Q;
Q.push((QueNode) {
s,1
});
for(int i=1; i<=n; i++)
for(int j=0; j<=n; j++)
dist[i][j]=1e17;
inque[s][1]=1;
dist[s][1]=0;
while(!Q.empty()) {
QueNode Now=Q.front();
Q.pop();
inque[Now.u][Now.d]=0;
for(int i=0; i<edges[Now.u].size(); i++) {
Edge& e=edges[Now.u][i];
int Next=e.to;
if(dist[Next][Now.d+1]>dist[Now.u][Now.d]+e.dist) {
dist[Next][Now.d+1]=dist[Now.u][Now.d]+e.dist;
if(!inque[Next][Now.d+1]) {
inque[Next][Now.d+1]=1;
Q.push((QueNode) {
Next,Now.d+1
});
}
}
}
}
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
}
Spfa(1);
for(int i=1; i<=n; i++)
if(dist[n][i]<1e17)ans=min(ans,dist[n][i]/i);
printf("%0.4lf\n",ans);
return 0;
}
