【迪杰斯特拉双关键字最短路】【HDU3790】【最短路径问题】

题目大意:

给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。

只需要再更新的时候判断一下就好

void dijstra(int s)
{
dist[s]=0;
for(int i=1;i<=n;i++)
{
s=findmin();
visit[s]=1;
for(int j=1;j<=n;j++)
{
if(dist[j]>dist[s]+MAP[s][j])
{
dist[j]=dist[s]+MAP[s][j];
val[j]=val[s]+w[s][j];
}
else if(dist[j]==dist[s]+MAP[s][j]&&val[j]>val[s]+w[s][j])
val[j]=val[s]+w[s][j];
}
}
}

完整代码如下:

/*
1.有重边
2.忘记是无向图了
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1000+5;
int n,m;
int MAP[maxn][maxn];
int w[maxn][maxn];
int dist[maxn];
int visit[maxn];
int val[maxn];
int ss,tt;
void input()
{
int a,b,d,q;
memset(MAP,0x3f,sizeof(MAP));
memset(dist,0x3f,sizeof(dist));
memset(w,0,sizeof(w));
memset(visit,0,sizeof(visit));
memset(val,0,sizeof(val));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&d,&q);
if(MAP[a][b]>d)
{
MAP[a][b]=MAP[b][a]=d;
w[a][b]=w[b][a]=q;
}
}
cin>>ss>>tt;
}
int findmin()
{
int min=INF,ANS=0;
for(int i=1;i<=n;i++)
{
if(visit[i]==0)
{
if(dist[i]<min)
{
min=dist[i];
ANS=i;
}
}
}
return ANS;
}
void dijstra(int s)
{
dist[s]=0;
for(int i=1;i<=n;i++)
{
s=findmin();
visit[s]=1;
for(int j=1;j<=n;j++)
{
if(dist[j]>dist[s]+MAP[s][j])
{
dist[j]=dist[s]+MAP[s][j];
val[j]=val[s]+w[s][j];
}
else if(dist[j]==dist[s]+MAP[s][j]&&val[j]>val[s]+w[s][j])
val[j]=val[s]+w[s][j];
}
}
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
void solve()
{
dijstra(ss);
printf("%d %d\n",dist[tt],val[tt]);
}
int main()
{
// init();
while(cin>>n>>m&&n&&m)
{
input();
solve();
}
}
上一篇:Entity Framework 5.0系列之Code First数据库迁移


下一篇:[JZOJ5836] Sequence