ねつなみ

go to the problem
テンプレートの問題はまたどんな問題を書いてQWQを解きます
dijkstra(欲張り)

#include
#include
#include
#include
using namespace std;
int t,c,ts,te,rs,re;
int a[3000][3000];
int d[3000];
bool used[3000];
const int inf=1047483647; 
int main()
{
    cin>>t>>c>>ts>>te;
    for(int i=1;i<=t;++i)
       for(int j=1;j<=t;++j)
            a[i][j]=inf;
    for(int i=1;i<=c;++i)
    {
        cin>>rs>>re;
        cin>>a[rs][re];
        a[re][rs]=a[rs][re];
    }
    memset(d,63,sizeof(d));
    d[ts]=0;
    for(int j=1;j<=t;++j)
    {
        int sum=inf,k=0;
        for(int i=1;i<=t;++i) //        d    
        {
            if((!used[i])&&(d[i]if(k==0) break;
        for(int i=1;i<=t;++i)           
        {
            if(d[k]+a[k][i]true;
    }
    cout<return 0;
}

dijkstra+スタック最適化

#include
#include
#include
#include
#include
#include
using namespace std;

int T,C,f,t,d,ts,te,cnt;
int first[2510],next[13000],de[2510];
bool used[2510];
struct maple{
    int f,t,d;
}Rode[13000];
struct Edge{
    int f,d;
    bool operator const Edge &a)const{
       return a.d  q;

void build(int f,int t,int d)
{
    Rode[++cnt]=(maple){ f,t,d};
    next[cnt]=first[f];
    first[f]=cnt;
}

int main()
{
    scanf("%d%d%d%d",&T,&C,&ts,&te);
    for(int i=1;i<=C;++i)
    {
        scanf("%d%d%d",&f,&t,&d);
        build(f,t,d);
        build(t,f,d);
    }
    q.push((Edge){ ts,0 });
    memset(de,63,sizeof(de));
    de[ts]=0;
    while(!q.empty())
    {
        Edge a=q.top();
        q.pop();
        while(!q.empty()&&used[a.f]) a=q.top(),q.pop();
        used[a.f]=1;
        if(a.f==te) 
        {
            cout<break;
        }
        for(int i=first[a.f];i;i=next[i])
            if(!used[Rode[i].t]&&a.d+Rode[i].dreturn 0;
}

SPFA

#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=100010;

int T,C,ts,te,cnt,x,y,z;
int first[MAXN],next[MAXN],de[MAXN];
bool used[MAXN];
struct Edge{
    int f,e,d;
}rode[MAXN];

queue<int> q;

void build(int f,int t,int d)
{
    rode[++cnt]=(Edge){ f,t,d};
    next[cnt]=first[f];
    first[f]=cnt;
}
void go()
{
    while(!q.empty())
    q.pop();
    q.push(ts);
    de[ts]=0;
    used[ts]=1;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        used[v]=0;
        for(int i=first[v];i!=-1;i=next[i])
        {
            int u=rode[i].e;
            if(de[u]>(de[v]+rode[i].d))
            {
                de[u]=de[v]+rode[i].d;  
                if(!used[u])
                {
                   q.push(u);
                   used[u]=1;
                }
            }
        }
    }

}
int main()
{
    memset(first,-1,sizeof(first));
    memset(next,-1,sizeof(next));
    memset(used,0,sizeof(used));
    memset(de,63,sizeof(de));
    scanf("%d%d%d%d",&T,&C,&ts,&te);
    for(int i=1;i<=C;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        build(x,y,z);
        build(y,x,z);
    }
    go();
    printf("%d",de[te]);
    return 0;
}