题目链接 LeetCode XXX

我遇到了不会问题。

错误的代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<sstream>

using namespace std;
const int o=1e5+10;
int e[o],ne[o],idx,h[o],w[o],d[o],dj[o];
bool st[o];
int n,m,cnt;
typedef pair<int ,int> PII;
void add(int a,int b,int c)
{
    e[idx]=b;ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra()
{
    memset(d,0x3f,sizeof d);
    d[1]=10000;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({10000,1});

    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();

        int dis=t.first,k=t.second;
        if(st[k]) continue;
        st[k]=true;

        for(int i=h[k];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(abs(dj[h[k]]-dj[j])<=n&&d[j]>dis+w[i])
            {
                d[j]=dis+w[i];
                heap.push({d[j],j});
            }
        }
    }
    int maxn=0x3f3f3f3f;
    for(int i=1;i<=m;i++)
    {
        if(d[i]<maxn) maxn=d[i];
    }
    cout<<maxn<<endl;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        dj[++cnt]=y;
        if(z==0){
            add(i,i,x);
        }
        else{
            add(i,i,x);
            for(int j=1;j<=z;j++){
                int p,q;
                cin>>p>>q;
                add(i,p,q);
                add(p,i,q);
            }
        }
    }
    dijkstra();
    return 0;
}

编译器报了什么错误？无错误

题目描述

农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。

把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。

当然，他将付出额外的费用在奶牛上。

农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。

他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。

给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

数据保证至少存在一个牧场和所有牛所在的牧场连通。

输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。

第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。

第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。

输出格式
共一行，输出奶牛必须行走的最小的距离和。

数据范围
1≤N≤500,
2≤P≤800,
1≤C≤1450,
1≤D≤255

样例

输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;
typedef long long ll;
int mc[12000],e[12000],ne[12000],idx,w[12000],d[12000],n,p,m,h[12000];
bool st[12000];
typedef pair<int ,int> PII;
void add(int a,int b,int c)//建图;
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra()//板子;
{
    ll sum;存储各位牛马到放黄油牧场的距离;
    ll minn=0x3f3f3f3f;//比较哪个牧场的距离最短,最后输出.
    for(int i=1;i<=p;i++)//有p个牧场;
    {
        memset(st,false,sizeof st);//同下;
        memset(d,0x3f,sizeof d);//每次初始化
        d[i]=0;//i牧场到自身的距离为0;

        priority_queue<PII,vector<PII>,greater<PII>> heap;
        heap.push({0,i});

        while(heap.size())
        {
            PII t=heap.top();
            heap.pop();

            int dis=t.first,k=t.second;
            if(st[k]) continue;
            st[k]=true;
            for(int j=h[k];j!=-1;j=ne[j])
            {
                int k=e[j];
                if(d[k]>dis+w[j])
                {
                    d[k]=dis+w[j];
                    heap.push({d[k],k});
                }
            }
        }
        //此时已求出每个牧场到i牧场的最短距离;
        sum=0;
        for(int j=1;j<=n;j++)
        {
            sum+=d[mc[j]];
        }
        if(sum<minn) minn=sum;
    }
    printf("%lld",minn);
}
int main()
{
    cin>>n>>p>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) cin>>mc[i]; 
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    dijkstra();
    return 0;
}

题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。

样例

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

C++ 代码

//堆优化系列;
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
const int N=2e5;
int e[N], d[N],ne[N], idx,n, m, w[N], h[N];
bool st[N];
typedef pair<int, int> PII;
void add(int a,int b,int c)//建图必备;
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra()
{
    memset(d,0x3f,sizeof d);如果走不到那个点的话,就是正无穷;
    d[1]=0;点1到点1的距离为0;

    priority_queue<PII ,vector<PII>, greater<PII>> heap;//greater是一个排序函数,用小根堆;
    heap.push({0,1});第一维代表最短距离，第二维代表当前点;


    while(heap.size()模板;
    {
        PII t=heap.top();//
        int dis=t.first,k=t.second;
        heap.pop();
        if(st[k]) continue;
        st[k]=true;

        for(int i=h[k];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]>dis+w[i]){
                d[j]=dis+w[i];
                heap.push({d[j],j});
            }
        }
    }

    if(d[n]==0x3f3f3f3f) puts("-1");
    else cout<<d[n]<<endl;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a, b, c);建图;
    }
    dijkstra();
    return 0;
}

题目描述

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！

他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。

农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含 C 条直接连接 2 个城镇的道路。

每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。

求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。
输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;

第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs,Re,Ci。

输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。

数据保证至少存在一条道路。

数据范围
1≤T≤2500,
1≤C≤6200,
1≤Ts,Te,Rs,Re≤T,
1≤Ci≤1000

样例

输入样例：
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例：
7

C++ 代码

//没啥区别，只是换了一下起点和终点,以及图变成二向图;
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=30000;
int e[N],ne[N],h[N],idx,d[N],w[N],n,m,qd,zd;//注意e,ne,w所存的是边,所以要大于6200;(懒的改M);
bool st[N];
typedef pair<int,int> PII;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra()//模板;
{
    //int minn=min(qd,zd);//同下;
    //int maxn=max(qd,zd);//当时脑残了;
    memset(d,0x3f,sizeof d);
    d[qd]=0;//起点到起点的距离为0;

    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,qd});

    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int dis=t.first,k=t.second;
        if(st[k]) continue;
        st[k]=true;

        for(int i=h[k]; i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]>dis+w[i])
            {
                d[j]=dis+w[i];
                heap.push({d[j],j});
            }
        }
    }
    cout<<d[zd]<<endl;
}
int main()
{
    cin>>n>>m>>qd>>zd;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);//因为是双向图，所以从x到y和从y到x两条边;
    }
    dijkstra();
    return 0;
}
//第一篇题解，有错清指出

题目链接 信息学奥赛一本通1199

我遇到了无法输出问题。

错误的代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=10;
string s;
bool st[100001];
char a[N];
void dfs(int u){
    int len=s.size();
    if(u==len){
        for(int i=0;i<len;i++) cout<<a[i];

        puts("");
        return;
    }
    for(int i=0;i<len;i++)
        if(!st[i])
        {
            a[i]=s[u];
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
}
int main()
{
    cin>>s;

    dfs(0);

    return 0;
}

无报错，只是不能输出

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;
const int N=20;
int cat[N],sum[N];
int ans=N;
int n,w;
void dfs(int u,int k)
{
    if(k>=ans) return;
    if(u==n){
        ans=k;
        return;
    }
    for(int i=0;i<k;i++)
        if(sum[i]+cat[u]<=w)
        {
            sum[i]+=cat[u];
            dfs(u+1,k);
            sum[i]-=cat[u];
        }
    sum[k]=cat[u];
    dfs(u+1,k+1);
    sum[k]=0;
}
int main()
{
    cin>>n>>w;

    for(int i=0;i<n;i++)
        cin>>cat[i];

    sort(cat,cat+n);
    reverse(cat,cat+n);
    dfs(0,0);
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

void qmi(ll a,ll b,ll c)
{
    ll res=1;
    while(b){
        if(b&1){
            res=(ll)res*a%c;
        }
        a=(ll)a*a%c;
        b >>= 1;
    }
    cout<<res%c<<endl;
}
int main()
{
    int a,b,c;
    //freopen("a^b.in","r",stdin);
    //freopen("a^b.out","w",stdout);
    cin>>a>>b>>c;
    qmi(a,b,c);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while( t --)
    {
        int k,l;
        scanf("%d %d",&k,&l);
        while(l%k==0){
            l=l/k;
        }
        if(l==1) cout<<"YES"<<endl;
        else cout<< "NO" <<endl;
    }
    return 0;
}

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
    long long k,i,sum=0,h;
    cin>>k;
    for(i=1;;i++)
    {
        sum+=(i*i);
        h+=i;
        if(h>k)
        {
            sum-=(h-k)*i;
            h=k;
        }
        if(h==k)
        {
            break;
        }
    }
    cout<<sum<<endl;
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N];

int bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n - 1][m - 1];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}