데이터 구조 실험의 도 론 7: 당나귀 친구 계획

데이터 구조 실험의 도 론 7: 당나귀 친구 계획
Time Limit: 1000MS Memory limit: 65536K
제목 설명
베테랑 당나귀 친구 로 서 샤 오 신 은 소 중 히 간직 하고 있 는 자가 운전 노선 도 를 가지 고 있 습 니 다. 그림 에는 전국 각 도시 간 의 고속도로 거리 와 도로 요금 상황 이 상세 하 게 표시 되 어 있 습 니 다. 지금 은 프로그램 을 만들어 목적지 에서 목적지 까지 의 가장 짧 은 경 로 를 찾 아 보 세 요. 여러 경로 가 가장 짧 으 면 통행 료 가 가장 적은 경 로 를 출력 하 세 요.
입력
연속 T 조 데이터 입력, 각 조 가 입력 한 데이터 의 첫 줄 은 네 개의 정수 N, M, s, d 를 제시 합 니 다. 그 중에서 N (2 < = N < = 500) 은 도시 수량 이 고 도시 번 호 는 0 ～ N - 1 이 며 M 은 도시 간 고속도로 의 수량 입 니 다. s 는 출발지 의 도시 번호 이 고 d 는 목적지 의 도시 번호 입 니 다.그 다음 에 M 행 은 각 줄 에 고속도로 정 보 를 제공 하여 도시 1, 도시 2, 고속도로 길이, 요금 액 을 나타 내 고 중간 에 빈 칸 으로 간격 을 두 며 숫자 는 모두 정수 이 고 500 을 초과 하지 않 으 며 입력 데 이 터 는 모두 해 제 될 것 을 보증한다. 
출력
같은 줄 에서 출력 경로 의 길이 와 비용 총액, 데이터 간 에 빈 칸 으로 간격 을 둡 니 다. 
예제 입력

1
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

예제 출력

3 40

제시 하 다.
 
근원
xam 
예제 프로그램
 

#include
#include
#include
#define N 1000
#define INF 0x3f3f3f3f
typedef struct
{
    int len;
    int dol;
}node;
node mp[N][N];
void floyd(int n)
{
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            for(int k = 0;k < n;k++)
            {
                if(mp[j][k].len > mp[j][i].len + mp[i][k].len)
                {
                    mp[j][k].len = mp[j][i].len + mp[i][k].len;
                    mp[j][k].dol = mp[j][i].dol + mp[i][k].dol;
                }
                else if(mp[j][k].len == mp[j][i].len + mp[i][k].len)
                {
                    if(mp[j][k].dol > mp[j][i].dol + mp[i][k].dol)
                    {
                        mp[j][k].dol = mp[j][i].dol + mp[i][k].dol;
                    }
                }
            }
        }
    }
}
int main()
{
    int t,n,m,s,d;
    int u,v,w,q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d %d",&n,&m,&s,&d);
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < n;j++)
            {
                if(i != j)
                {
                    mp[i][j].len = mp[i][j].dol = INF;
                }
                else
                    mp[i][j].len = mp[i][j].dol = 0;
            }
        }
        for(int i = 0;i < m;i++)
        {
            scanf("%d %d %d %d",&u,&v,&w,&q);
            if(mp[u][v].len > w)
            {
                mp[u][v].len = w;
                mp[v][u].len = w;
                mp[u][v].dol = q;
                mp[v][u].dol = q;
            }
        }
        floyd(n);
        printf("%d %d
",mp[s][d].len,mp[s][d].dol);
    }
    return 0;
}