生活随笔
收集整理的這篇文章主要介紹了
1072 Gas Station (30 分)【难度: 中 / 知识点: Dijkstra + 枚举】
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072
題目說的不清不楚，應(yīng)該直接說要建一個(gè)加油站，候選位置有以下幾個(gè)。沒說建一個(gè)還是兩個(gè)。
分析：
就是枚舉每一個(gè)加油站的候選位置，求最短路。然后根據(jù)題意找到最優(yōu)解即可。這里的話點(diǎn)很少，直接樸素版的Dijkstra。
注意: 加油站的候選位置編號是字符串，需要將其映射要數(shù)字。
還要注意精度問題，加一特別小的數(shù)保持精度。
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e3+50;
int g
[N
][N
],st
[N
],dist
[N
],n
,m
,k
,d
;
int get(string s
)
{if(s
[0]=='G') return n
+stoi(s
.substr(1));return stoi(s
);
}
bool Dijkstra(int startx
,int &temp_min
,int &temp_sum
)
{memset(dist
,0x3f,sizeof dist
); dist
[startx
]=0;memset(st
,0,sizeof st
);for(int i
=0;i
<n
+m
;i
++){int t
=-1;for(int j
=1;j
<=n
+m
;j
++) if(!st
[j
]&&(t
==-1 || dist
[j
]<dist
[t
])) t
=j
;st
[t
]=1;for(int j
=1;j
<=n
+m
;j
++) dist
[j
]=min(dist
[j
],dist
[t
]+g
[t
][j
]);}temp_min
=1e9,temp_sum
=0;for(int i
=1;i
<=n
;i
++) {if(dist
[i
]>d
) return false;temp_sum
+=dist
[i
];temp_min
=min(temp_min
,dist
[i
]);}return true;
}
int main(void)
{cin
>>n
>>m
>>k
>>d
;memset(g
,0x3f,sizeof g
);for(int i
=0;i
<k
;i
++){string x
,y
;int a
,b
,c
; cin
>>x
>>y
>>c
;a
=get(x
),b
=get(y
);g
[a
][b
]=g
[b
][a
]=min(g
[a
][b
],c
);}int flag
=0,minv
=0,sum
=1e9;for(int i
=n
+1;i
<=n
+m
;i
++){int temp_min
=0,temp_sum
=0;if(!Dijkstra(i
,temp_min
,temp_sum
)) continue;if(temp_min
>minv
) flag
=i
,minv
=temp_min
,sum
=temp_sum
;else if(temp_min
==minv
&&temp_sum
<sum
) flag
=i
,sum
=temp_sum
;}if(flag
) printf("G%d\n%.1lf %.1lf",flag
-n
,1.0*minv
,sum
*1.0/(n
)+1e-7);else puts("No Solution");return 0;
}
總結(jié)
以上是生活随笔為你收集整理的1072 Gas Station (30 分)【难度: 中 / 知识点: Dijkstra + 枚举】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
