題意：
? ? ? 給你起點終點，和一些加油站，和每次加油后的最大行駛距離，問你從起點到終點最少加油次數，要求兩點之間必須走直線，見到加油站必須加油，也就是說如果想從a走到b,那么a,b連線上的加油站必須加油。

思路：
? ? ? 關鍵就是處理a,b,之間的點必須加油這個問題，我們可以排序，x小的或者x相等y小的在前面，然后枚舉每條邊，對于每個點為起點的邊如果當前的斜率出現過，那么我們就可以不加這條邊（或者是在費用上增加1后加上這條邊），不加的原因是我們可以再后面加，比如a -> b ->c 我們可以 a ->b ,然后b->c，（也可以a->c 距離+1），標記每一個點為起點的斜率，斜率出現過就不加了，標記斜率可以用容器，總的建圖時間復雜度是

O(n*n*log(n)) log(n)是因為map操作需要一個log級的時間復雜度。

斜率相同直接跳過

#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #include<math.h> #include<map>#define N_node 1000 + 100 #define N_edge 1000000 + 1000 #define INF 0x3f3f3f3f using namespace std;typedef struct {int to ,next ,cost; }STAR;typedef struct {double x ,y;int id; }NODE;STAR E[N_edge]; NODE node[N_node]; int list[N_node] ,tot; int s_x[N_node]; map<double ,int>hash;void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }double dis(NODE a ,NODE b) {double x = (a.x - b.x) * (a.x - b.x);double y = (a.y - b.y) * (a.y - b.y);return sqrt(x + y); }bool camp(NODE a ,NODE b) {return a.x < b.x || a.x == b.x && a.y < b.y; }void spfa(int s ,int n) {int mark[N_node] = {0};for(int i = 0 ;i <= n ;i ++)s_x[i] = INF;queue<int>q;q.push(s);mark[s] = 1 ,s_x[s] = 0;while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){int xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}} }int main () {int n ,i ,j ,t;double L;scanf("%d" ,&t);while(t--){scanf("%d %lf" ,&n ,&L);scanf("%lf %lf" ,&node[1].x ,&node[1].y);scanf("%lf %lf" ,&node[2].x ,&node[2].y);node[1].id = 1 ,node[2].id = 2;for(n += 2 ,i = 3 ;i <= n ;i ++){scanf("%lf %lf" ,&node[i].x ,&node[i].y);node[i].id = i;}sort(node + 1 ,node + n + 1 ,camp);for(i = 1 ;i <= n ;i ++){hash.clear();for(j = i + 1 ;j <= n ;j ++)if(dis(node[i] ,node[j]) <= L){double xx = node[j].x - node[i].x;double yy = node[j].y - node[i].y;double v = xx == 0 ? -INF : yy / xx;if(hash[v]) continue;hash[v] = 1;add(node[i].id ,node[j].id ,hash[v]);add(node[j].id ,node[i].id ,hash[v]);}}spfa(1 ,n); int ans = s_x[2];ans == INF ? puts("impossible") : printf("%d\n" ,ans - 1);}return 0; }

出現過的斜率那么就累加1的（跟上面的只有兩行不同，其他的相同）

#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #include<math.h> #include<map>#define N_node 1000 + 100 #define N_edge 1000000 + 1000 #define INF 0x3f3f3f3f using namespace std;typedef struct {int to ,next ,cost; }STAR;typedef struct {double x ,y;int id; }NODE;STAR E[N_edge]; NODE node[N_node]; int list[N_node] ,tot; int s_x[N_node]; map<double ,int>hash;void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }double dis(NODE a ,NODE b) {double x = (a.x - b.x) * (a.x - b.x);double y = (a.y - b.y) * (a.y - b.y);return sqrt(x + y); }bool camp(NODE a ,NODE b) {return a.x < b.x || a.x == b.x && a.y < b.y; }void spfa(int s ,int n) {int mark[N_node] = {0};for(int i = 0 ;i <= n ;i ++)s_x[i] = INF;queue<int>q;q.push(s);mark[s] = 1 ,s_x[s] = 0;while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){int xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}} }int main () {int n ,i ,j ,t;double L;scanf("%d" ,&t);while(t--){scanf("%d %lf" ,&n ,&L);scanf("%lf %lf" ,&node[1].x ,&node[1].y);scanf("%lf %lf" ,&node[2].x ,&node[2].y);node[1].id = 1 ,node[2].id = 2;for(n += 2 ,i = 3 ;i <= n ;i ++){scanf("%lf %lf" ,&node[i].x ,&node[i].y);node[i].id = i;}sort(node + 1 ,node + n + 1 ,camp);memset(list ,0 ,sizeof(list)) ,tot = 1;for(i = 1 ;i <= n ;i ++){hash.clear();for(j = i + 1 ;j <= n ;j ++)if(dis(node[i] ,node[j]) <= L){double xx = node[j].x - node[i].x;double yy = node[j].y - node[i].y;double v = (xx == 0 ? -INF : yy / xx);//if(hash[v]) continue; hash[v] ++;add(node[i].id ,node[j].id ,hash[v]);add(node[j].id ,node[i].id ,hash[v]);}}spfa(1 ,n); int ans = s_x[2];ans == INF ? puts("impossible") : printf("%d\n" ,ans - 1);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4885 有 限制的最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。