最短路径问题
给你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 0
Sample Output
9 11
双权值问题,一个长度一个花费
按题目要求:要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的
读入数据时要注意一下,同时在判断长度和花费的时候与读入数据一致,都需要额外注意一下,刚开始的时候没有注意,然后就一直 TLE ,TLE 了几十发才注意到…孩子哭了
AC代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1010;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
int cost[N];
bool vis[N];
int st,ed;
struct Node{
int l;
int c;
}node[N][N];
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
memset(cost,0x3f,sizeof cost);
memset(vis,0,sizeof vis);
dist[st]=0;
cost[st]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,st});
// first 距离 second 点
while(heap.size())
{
int t=heap.top().second;
heap.pop();
if(vis[t]) continue;
vis[t]=true;
for(int i=1;i<=n;i++)
{
if(dist[i]>dist[t]+node[t][i].l)
{
dist[i]=dist[t]+node[t][i].l;
cost[i]=cost[t]+node[t][i].c;
heap.push({dist[i],i});
}
else if(dist[i]==dist[t]+node[t][i].l&&cost[i]>cost[t]+node[t][i].c)
{
cost[i]=cost[t]+node[t][i].c;
heap.push({dist[i],i});
}
}
}
cout<<dist[ed]<<" "<<cost[ed]<<endl;
}
int main()
{
while(cin>>n>>m&&n&&m)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
node[i][j].c=node[i][j].l=0x3f3f3f3f;
for(int i=1;i<=m;i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(node[a][b].l>c){
node[a][b].l=node[b][a].l=c;
node[a][b].c=node[b][a].c=d;
}else if(node[a][b].l==c){
node[a][b].c=node[b][a].c=min(d,node[a][b].c);
}
}
cin>>st>>ed;
dijkstra();
}
return 0;
}