道路 Road(百练，POJ)

本文主要是介绍道路 Road(百练，POJ)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接: 1724 -- ROADS (poj.org)

题目描述:

思路: 这题目乍一看，是一个含有2个标尺的单源最短路问题，挺难处理的。

既然没法直接用最短路处理，那我们就“记录信息”，将花费的时间也记录进dp数组，然后跑“状态最短路”。

用f[i][j] 表示到达点i 且 总花费时间为j的最短距离，然后跑堆优化的dijkstra算法就好。由于不含有负边权，因此可以搞一个vis数组，如果已经被确定为最小值的东西就不需要再被更新了。

总的时间复杂度大约是O(MlogM), 其中M=1e6.

参考代码:

//#include<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e4+10;
const int inf=0x3f3f3f3f;
int f[110][N];
int vis[110][N];
struct node{int x1; // 点 int y1; // 时间 int value; // 距离friend bool operator<(node xx,node yy){return xx.value > yy.value;}
};
priority_queue<node> q;
int k,n,m;
vector<node> edge[N];void dijkstra(){memset(f,0x3f,sizeof(f));memset(vis,0,sizeof(vis));f[1][0]=0;q.push(node{1,0,f[1][0]});while(!q.empty()){node cur=q.top();q.pop();int x=cur.x1; // 点 int y=cur.y1; // 时间 if(vis[x][y]) continue;vis[x][y]=1;int len=edge[x].size();for(int i=0;i<len;i++){int u=edge[x][i].x1; // 点 int v=edge[x][i].y1; // 时间int w=edge[x][i].value; // 距离 v=v+y;if(v>k) continue;if(vis[u][v]) continue;if(f[u][v]>f[x][y]+w){f[u][v]=f[x][y]+w;q.push(node{u,v,f[u][v]});}}}return ;
}int main(void){scanf("%d%d%d",&k,&n,&m);for(int i=1;i<=m;i++){int s,d,l,w;scanf("%d%d%d%d",&s,&d,&l,&w);edge[s].push_back(node{d,w,l});}dijkstra();int res=inf;for(int i=0;i<=k;i++){res=min(res,f[n][i]);}if(res==inf) printf("-1");else printf("%d",res);return 0;
}

这篇关于道路 Road(百练，POJ)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---