程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 1922: [Sdoi2010]大陸爭霸|dijkstra

1922: [Sdoi2010]大陸爭霸|dijkstra

編輯：C++入門知識

1922: [Sdoi2010]大陸爭霸|dijkstra

設d1[x],d2[x]為城市x的到達時間，可進入時間
max(d1[x],d2[x])為真實的進入時間
d[x]記錄城市x被多少個城市保護
每次堆中取出一個真實進入時間最小的城市
更新它所通往的城市的d1，保護城市的d2
保護城市的d–1
若d=0，則可入堆
復雜度(n+m)log2n

黃學長寫的比較清楚了，似乎很多人都用了矩陣存圖的樣子

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 11111111111111LL
#define ll long long
#define pa pair
#define N 80005
using namespace std;
int sc()
{
    int i=0; char c=getchar();
    while( c>'9' || c<'0' ) c=getchar();
    while( c>='0' && c<='9' )i=i*10+c-'0',c=getchar();
    return i;
}
ll d1[N],d2[N],d[N];
int Head[N],Nxt[N],Lst[N],vis[N];
int head[N],nxt[N],lst[N],v[N];
int n,m,tot,Tot;
priority_queue,greater >q;
void insert(int x,int y,int z)
{
    lst[++tot]=y;nxt[tot]=head[x];head[x]=tot;v[tot]=z;
}
void insert(int x,int y)
{
    d[y]++;Lst[++Tot]=y;Nxt[Tot]=Head[x];Head[x]=Tot;
}
void dijkstra()
{
    for(int i=1;i<=n;i++)d1[i]=inf;
    q.push(make_pair(d1[1]=d2[1]=0,1));
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x])continue;vis[x]=1;
        ll now=max(d1[x],d2[x]);
        for(int i=head[x];i;i=nxt[i])
            if(now+v[i]