[USACO09OCT]热浪Heat Wave

题目

https://www.luogu.org/problemnew/show/P1339

题解

这是Dijkstra算法真正的一道模板，只不过数组范围要开十倍，否则TLE。。。。。。
https://www.luogu.org/recordnew/lists?uid=151225&pid=P1339
这是我的TLE历程。。。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=25010;
inline int read()
{
    int f=1,num=0;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch==\'-\') f=-1; ch=getchar(); }
    while (isdigit(ch)) num=(num<<1)+(num<<3)+(ch^48), ch=getchar();
    return num*f;
}
int ver[maxn*2],edge[maxn*2],Next[maxn*2],head[maxn],len;
inline void add(int x,int y,int z)
{
    ver[++len]=y,edge[len]=z,Next[len]=head[x],head[x]=len;
}
priority_queue<pair<int,int> >q;
int v[maxn],dist[maxn];
void dijkstra(int s)
{
    memset(dist,0x3f,sizeof(dist));
    memset(v,0,sizeof(v));
    dist[s]=0,v[s]=1;
    q.push(make_pair(0,s));
    while (!q.empty())
    {
        int x=q.top().second;
        q.pop();
        v[x]=0;
        for (int i=head[x];i;i=Next[i])
        {
            int y=ver[i],z=edge[i];
            if (dist[y]>dist[x]+z)
            {
                dist[y]=dist[x]+z;
                if (!v[y]) v[y]=1,q.push(make_pair(-dist[y],y));
            }
        }
    }
}
int main()
{
    int n=read(),m=read(),s=read(),t=read();
    for (int i=1;i<=m;++i)
    {
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    dijkstra(s);
    printf(\"%d\\n\",dist[t]);
    return 0;
}

电车

题目

https://www.luogu.org/problemnew/show/P1346

题解

一道Floyed算法的模板，只不过把题中的开关转化成权值就行。

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
inline int read()
{
    int f=1,num=0;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch==\'-\') f=-1; ch=getchar(); }
    while (isdigit(ch)) num=(num<<1)+(num<<3)+(ch^48),ch=getchar();
    return num*f;
}
int lock[110][110];
int main()
{
    int n=read(),s=read(),e=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            lock[i][j]=inf,lock[i][i]=0;
    for (int i=1;i<=n;++i)
    {
        int t=read();
        for (int j=1;j<=t;++j)
        {
            int x=read();
            if (j==1) lock[i][x]=0;
            else lock[i][x]=1;
        }
    }
    for (int k=1;k<=n;++k)
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                lock[i][j]=min(lock[i][j],lock[i][k]+lock[k][j]);
    if (lock[s][e]==inf) puts(\"-1\\n\");
    else printf(\"%d\\n\",lock[s][e]);
    return 0;
}

最短路计数

题目

https://www.luogu.org/problemnew/show/P1144

题解

这道题就当做一个知识点，学会就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6;
const int mod=100003;
inline int read()
{
    int f=1,num=0;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch==\'-\') f=-1; ch=getchar(); }
    while (isdigit(ch)) num=(num<<1)+(num<<3)+(ch^48), ch=getchar();
    return num*f;
}
int ver[maxn*2],Next[maxn*2],head[maxn],len;
inline void add(int x,int y)
{
    ver[++len]=y,Next[len]=head[x],head[x]=len;
}
int dist[maxn],v[maxn],cnt[maxn];
void spfa()
{
    queue<int>q;
    memset(dist,0x3f,sizeof(dist));
    memset(v,0,sizeof(v));
    dist[1]=0,cnt[1]=1;
    v[1]=1,q.push(1);
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        v[x]=0;
        for (int i=head[x];i;i=Next[i])
        {
            int y=ver[i];
            if (dist[y]>dist[x]+1)
            {
                dist[y]=dist[x]+1;
                cnt[y]=cnt[x];
                if (!v[y]) v[y]=1,q.push(y);
            }
            else if (dist[y]==dist[x]+1)
            {
                cnt[y]+=cnt[x];
                cnt[y]%=mod;
            }
        }
    }
}
int main()
{
    int n=read(),m=read();
    for (int i=1;i<=m;++i)
    {
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    spfa();
    for (int i=1;i<=n;++i)
        printf(\"%d\\n\",cnt[i]);
    return 0;
}