程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 1922: [Sdoi2010]大陸爭霸|dijkstra

1922: [Sdoi2010]大陸爭霸|dijkstra

編輯：關於C++

設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]

關於C++

c++中static的用法詳解

C 語言的 static 關鍵字有三

POJ 2784 Buy or Build最小生成樹

Buy or Build Time Limit

C++ 實現高性能內存池

一、概述在 C/C++ 中，內存管理是一個非常棘手的問題，我

成為C++高手之提高可維護性

思路當前的Poker工程還能進一步改進：把只與撲克相關的各種

C++通過COM接口操作PPT

一、背景說明在VS環境下，開發C++代碼操作PPT，支持對

【C++探索之旅】第一部分第八課：傳值引用，文件源頭

內容簡介1、第一部分第八課：傳值引用，文件源頭2、第一部分第