hdu 4725 (The Short Path in Nya Graph) 최 단 길

이 문 제 는 데이터 범위 가 비교적 넓 습 니 다. 만약 에 폭력 적 인 건축 도가 T 를 인정 하면 작은 기술 이 필요 합 니 다. 저 는 너무 찌꺼기 입 니 다. 큰 소의 블 로 그 를 보고 알 게 되 었 습 니 다.쿠 앙 신 은 두 가지 생각 이 있어 요.
아이디어 1
2n 개의 점, 즉 층 마다 두 개의 점 으로 변 하 는 것 이다.n + 2 * i - 1 - > n + 2 * (i + 1), 도로 권 은 c;즉, 윗 층 n + 2 * (i + 1) - 1 - > n + 2 * i 를 가리 키 고 도로 권 은 c 이다.바로 다음 층 을 가리 키 는 것 이다.
만약 에 i 가 u 층 에 속한다 면 i - > n + 2 * u - 1, 도로 권 은 0 이 고 입 층 n + 2 * u - > i, 도로 권 은 0 이 고 출 층 에 m 개의 방향 이 있 으 며 건축 도 를 완성 합 니 다. 그 다음 에 가장 짧 은 길 입 니 다. dijkst + 더미 최적화 와 spfa 가 모두 가능 합 니 다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define msc(X) memset(X,-1,sizeof(X))
#define ms(X) memset(X,0,sizeof(X))
typedef long long LL;
using namespace std;
const int MAXN=1010010;
const int INF=0x3f3f3f3f;
int d[MAXN],tot,hd[MAXN];
bool vs[MAXN];
struct _Edge
{
    int to,c,next;
    bool operator < (const _Edge &a) const{
        return c>a.c;
    }
}edge[2*MAXN];
inline void addedge(int u,int v,int c)
{
    edge[tot].to=v;
    edge[tot].c=c;
    edge[tot].next=hd[u];
    hd[u]=tot++;
}
void Dijkst(int beg,int n)
{
    struct _Edge tmp;
    ms(vs);
    for(int i=1;i<=n;i++) d[i]=INF;
    priority_queue <struct _Edge> q;
    while(!q.empty()) q.pop();
    tmp.to=beg,tmp.c=0;
    d[beg]=0;
    q.push(tmp);
    while(!q.empty()){
        tmp=q.top();
        q.pop();
        int u=tmp.to;
        if(vs[u]) continue;
        vs[u]=true;
        for(int i=hd[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(!vs[v]&&d[v]>d[u]+edge[i].c)
                {tmp.c=d[v]=d[u]+edge[i].c;
                    tmp.to=v;
                    q.push(tmp);
                }
        }
    }
}
int main(int argc, char const *argv[])
{
    int t,ti=0;
    cin>>t;
    while(++ti<=t){
        int n,m,CT;
        msc(hd);
        tot=0;
        scanf("%d %d %d",&n,&m,&CT);
        for(int i=1;i<=n;i++) {
            int l;
            scanf("%d",&l);
            addedge(i,n+2*l-1,0);
            addedge(n+2*l,i,0);
            addedge(n+2*(i+1)-1,n+2*i,CT);
            addedge(n+2*i-1,n+2*(i+1),CT);
        }
        while(m--){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            addedge(a,b,c);
            addedge(b,a,c);
        }
        Dijkst(1,3*n);
        printf("Case #%d: ",ti );
        if(d[n]==INF) puts("-1");
        else printf("%d
",d[n] );
    }
    return 0;
}

아이디어 2. 업데이트 층 업데이트
하지만 자세 가 필요 하 다. 그렇지 않 으 면 시간 복잡 도가 높아진다.변 처럼 인접 표를 만들어 각 층 의 정 보 를 저장 합 니 다.그리고 각 점 을 업데이트 할 때 도 한 번 씩 층 의 모든 점 을 업데이트 합 니 다.코드나 는 쓰 지 않 았 다 =. = | | |