HDU - 3790 （双标准限制最短路径）最短路径问题
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
Input输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t)Output输出 一行有两个数， 最短距离及其花费。Sample Input
3 2 1 2 5 6 2 3 4 5 1 3 0 0Sample Output
9 11
这是一道加了限制的最短路径题~~其实就是在普通的最短路径的搜寻中多加了几个关于cost消费的判断而已~~以路径最短的优先~~相同的话就以消费最少优先。
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int m,n;
struct ***
{
int to;
int len;
int cos;
int ne;
}ed[100005];
int head[1005];
int cnt = 0;
int vis[1005];
int d[1005];
int cost[1005];
void add(int from, int to, int len, int cos)
{
ed[cnt].to = to;
ed[cnt].len = len;
ed[cnt].cos = cos;
ed[cnt].ne = head[from];
head[from] = cnt++;
}
void spfa(int x)
{
vis[x] = 1;
queue<int>q;
q.push(x);
d[x] = 0;
cost[x] = 0;
while (!q.empty())
{
int t = q.front();
q.pop();
for (int s = head[t]; ~s; s = ed[s].ne)
{
if (d[ed[s].to] > d[t] + ed[s].len)
{
d[ed[s].to] = d[t] + ed[s].len;
cost[ed[s].to] = cost[t] + ed[s].cos;
if (!vis[ed[s].to])
{
vis[ed[s].to] = 1;
q.push(ed[s].to);
}
}
else if (d[ed[s].to] == d[t] + ed[s].len)
{
cost[ed[s].to] = min(cost[ed[s].to], cost[t] + ed[s].cos);
}
}
vis[t] = 0;
}
}
void init()
{
memset(head, -1, sizeof(head));
for (int s = 1; s <= n; s++)
{
cost[s] = inf;
}
for (int s = 1; s <= n; s++)
{
d[s] = inf;
}
memset(vis, 0, sizeof(vis));
cnt = 0;
for (int s = 1; s <= n; s++)
{
head[s] = -1;
}
}
int main()
{
while (cin >> n >> m&&n+m)
{
init();
while (m--)
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
add(b, a, c, d);
}
int a, b;
cin >> a >> b;
// cout << d[b] << " " << cost[b] << endl;
spfa(a);
cout << d[b] << " " << cost[b] << endl;
}
return 0;
}
盒马工作强度 28人发布
查看5道真题和解析
投递华为等公司10个岗位
