HDU - 항 저 우 전기 - 3790 - 최 단 경로 문제

질문
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9418 Accepted Submission(s): 2874
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

    SPFA

#include 
#include 
#include 
#include 
#define Max 0xfffffff
using namespace std;
int n,m,d[1111],p[1111];	//d   ，p   
bool qwe[1111];	//        
struct ssss
{
    int x,y;
}s[1111][1111];	//  
queue<int> q,qq;
void SPFA()
{
    int a,i;
    while(!q.empty())	//      
    {
        a=q.front();	//      
        q.pop();	//    
        qwe[a]=true;	//      
        for(i=1;i<=n;i++)	//         
        if(i!=a)
        {
            if(d[i]>d[a]+s[a][i].x)	//             
            {
                d[i]=d[a]+s[a][i].x;
                p[i]=p[a]+s[a][i].y;
                if(qwe[i])	//        ，         
                {
                    q.push(i);
                    qwe[i]=false;
                }
            }else if(d[i]==d[a]+s[a][i].x&&p[i]>p[a]+s[a][i].y)
            p[i]=p[a]+s[a][i].y;
        }
    }
}
int main (void)
{
    int i,j,a,b,c,e;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        q=qq;
        for(i=1;i<=n;i++)
        {
            qwe[i]=true;
            d[i]=p[i]=Max;
            for(j=1;j<=i;j++)
            s[i][j].x=s[i][j].y=s[j][i].x=s[j][i].y=Max;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&e);
            if(s[a][b].x>c)	//      
            {
                s[a][b].x=s[b][a].x=c;
                s[a][b].y=s[b][a].y=e;
            }
        }
        scanf("%d%d",&a,&b);
        d[a]=p[a]=0;
        qwe[a]=false;
        q.push(a);
        SPFA();
        printf("%d %d
",d[b],p[b]);
    }
    return 0;
}

         SPFA     ，     dijkstra，              ，       ，           ，

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 2544 최 단 로 (dijkstra 또는 Floyd 또는 bellman 또는 spfa)

여러 그룹의 데 이 터 를 입력 하 십시오.각 조 의 데이터 첫 줄 은 두 개의 정수 N, M (N & lt; 100, M & gt; = 10000) 이 고 N 은 청 두 의 거리 에 몇 개의 길목 이 있 고 1 로...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU - 항 저 우 전기 - 3790 - 최 단 경로 문제

좋은 웹페이지 즐겨찾기