程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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]

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved