HDU 3790 최 단 경로 문제 (BFS)

질문
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 36674    Accepted Submission(s): 10746
 
Problem Description
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
Output
한 줄 을 출력 하 는 데 는 두 개의 수가 있 는데, 가장 짧 은 거리 와 비용 이 든다.
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9
11
Source
저장 성 컴퓨터 대학원 재시험
[분석]디 제 스 트 라 템 플 릿 문제 입 니 다. 하지만 최근 bfs 를 풀 고 있 습 니 다. bfs 로 풀 고 싶 었 습 니 다. 어 제 는 정말 wa 가 계속 와 주 었 습 니 다. 과연 새로운 하루 의 새로운 아이디어 입 니 다. 제출 하면 A 입 니 다. 가장 중요 한 것 은 옆 에 있 는 두 개의 가중치 가 중복 될 수 있다 는 것 입 니 다. 입력 할 때마다 상황 에 따라 가중치 업데이트 여 부 를 판단 하고 결정 해 야 합 니 다. 그 다음 에 4 개의 배열 을 열 어 각각 표를 작성 하 는 것 입 니 다.두 점 사이 의 거리 와 비용, 그리고 출발점 에서 목표 점 까지 의 거리 와 비용 을 보 여 줍 니 다. 이 배열 들 은 항상 상황 에 따라 갱신 되 어야 합 니 다. 언제 입단 합 니까? 거 리 를 갱신 할 때 사용 하지 않 습 니 다. 문 제 는 가장 짧 은 거 리 를 요구 하기 때 문 입 니 다. 여러 개 를 가 봤 을 때 가장 적은 비용 을 선택 할 수 있 습 니 다. 하지만 우 리 는 매번 가장 작은 것 을 선택 합 니 다.
요컨대 이것 은 매우 쉽 지 않 은 A 의 코드 이다.ˇ‸ˇ•｡)…  이것 은 슬 픈 이야기 다.
【 코드 】

#include
using namespace std;
const int maxn=1e3+5;
int dis[maxn][maxn];
int money[maxn][maxn];
int dd[maxn],mm[maxn];
int n,m,s,t;
#define INF 0x3f3f3f3f

void bfs(int s)
{
	memset(dd,INF,sizeof(dd));
	memset(mm,INF,sizeof(mm));
	queueq;
	q.push(s);
	dd[s]=0;
	mm[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(dd[i]>dd[x]+dis[x][i])
			{
				dd[i]=dd[x]+dis[x][i];
				mm[i]=mm[x]+money[x][i];
				q.push(i);
			}
			else if(dd[i]==dd[x]+dis[x][i])
				mm[i]=min(mm[i],mm[x]+money[x][i]);
		}
	}
}
int main() 
{
	while(~scanf("%d%d",&n,&m)&&n&&m)
	{
		int a,b,d,p;
		memset(dis,INF,sizeof(dis));
		memset(money,INF,sizeof(money));
		for(int i=0;id)
			{
				money[a][b]=money[b][a]=p;
				dis[a][b]=dis[b][a]=d;
			}
			else if(dis[a][b]==d&&p