hdu--3790
3951 ワード
最短パスの問題
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 18738 Accepted Submission(s): 5581
Problem Description
n個の点をあげて、m本は縁がなくて、各辺はすべて長さdと費用pがあって、あなたに起点sの終点tをあげて、起点から終点までの最短距離とその費用を出力することを要求して、もし最短距離に複数のルートがあるならば、出力の費用は最も少ないです.
Input
n,m,点の番号を1~nと入力し,次いでm行とし,行ごとに4個の数a,b,d,pを入力し,aとbの間に辺があり,その長さはdであり,費用はpであることを示す.最後の行は2つの数s,tである.始点s、終点.nとmが0の場合に入力が終了します.
(1
Output
出力の1行には2つの数があり、最短距離とその費用がかかります.
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 18738 Accepted Submission(s): 5581
Problem Description
n個の点をあげて、m本は縁がなくて、各辺はすべて長さdと費用pがあって、あなたに起点sの終点tをあげて、起点から終点までの最短距離とその費用を出力することを要求して、もし最短距離に複数のルートがあるならば、出力の費用は最も少ないです.
Input
n,m,点の番号を1~nと入力し,次いでm行とし,行ごとに4個の数a,b,d,pを入力し,aとbの間に辺があり,その長さはdであり,費用はpであることを示す.最後の行は2つの数s,tである.始点s、終点.nとmが0の場合に入力が終了します.
(1
Output
出力の1行には2つの数があり、最短距離とその費用がかかります.
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
:http://acm.hdu.edu.cn/showproblem.php?pid=3790
:
: , . val[] . val[] .
:
#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
struct stu
{
int f,to,ne,l,s;
};
stu edge[100010*2];
int head[1010];
int vist[1010];
int num,n;
int dfn[1010];
int val[1010];
void inin()
{
num=0;
memset(head,-1,sizeof(head));
}
void add(int a,int b,int c,int d)
{
stu E={a,b,head[a],c,d};
edge[num]=E;
head[a]=num++;
}
void spfa(int u)
{
memset(dfn,0x3f,sizeof(dfn));
memset(vist,0,sizeof(vist));
memset(val,0,sizeof(val));
dfn[u]=0;
vist[u]=1;
//val[u]=0;
int v;
queue<int>q;
while(!q.empty())
{
q.pop();
}
q.push(u);
while(!q.empty())
{
v=q.front() ;
q.pop();
vist[v]=0;
for(int i=head[v];i!=-1;i=edge[i].ne)
{
int w=edge[i].to;
if(dfn[w]>edge[i].l+dfn[v])
{
dfn[w]=edge[i].l+dfn[v];//
val[w]=val[v]+edge[i].s;
if(!vist[w])
{
q.push(w);
vist[w]=1;
}
}
if(dfn[w]==edge[i].l+dfn[v]&&val[w]>val[v]+edge[i].s)
{
val[w]=val[v]+edge[i].s;
if(!vist[w])
{
q.push(w);
vist[w]=1;
}
}// ,
}
}
}
int main()
{
int m,a,b,c,d,star,end;
while(scanf("%d%d",&n,&m),n|m)
{
inin();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
add(a,b,c,d);
add(b,a,c,d);
}
scanf("%d%d",&star,&end);
spfa(star);
printf("%d %d
",dfn[end],val[end]);
}
return 0;
}