备战快速复习--day12

几个要点

• 初始化d[s]=0，c[s]=0
• 每次找到u以后vis[u]=true
• 使用g[x][y]>0判断有没有边，那么就需要初始化为0，不然有的评测默认不是0.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int st,ed,n,m;
int d[1000],c[1000];
int G[1000][1000]={0},cost[1000][1000]={0};
bool vis[1000]={false};
vector<int>pre[1000];
const int INF=100000;
void Dijkstra(int s)
{
    fill(d,d+n,INF);
    fill(c,c+n,INF);
    d[s]=0;
    c[s]=0;
    for(int i=0;i<=n-1;i++)
        pre[i].push_back(i);
    for(int i=0;i<=n-1;i++)
    {
        int u=-1;
        int minnum=INF;
        for(int j=0;j<=n-1;j++)
        {
            if(vis[j]==false && d[j]<minnum)
            {
                minnum=d[j];
                u=j;
            }
        }
        if(u==-1)
            return;
        vis[u]=true;
        for(int j=0;j<=n-1;j++)
        {
            if(vis[j]==false && G[u][j]>0)
            {
                if(d[j]>d[u]+G[u][j])
                {
                    d[j]=d[u]+G[u][j];
                    c[j]=c[u]+cost[u][j];
                    pre[j].clear();
                    pre[j].push_back(u);
                    //printf("j:%d u:%d part1:%d
",j,u,pre[j][0]);
                }
                else if(d[j]==d[u]+G[u][j] && c[j]>c[u]+cost[u][j])
                {
                    c[j]=c[u]+cost[u][j];
                    pre[j].clear();
                    pre[j].push_back(u);
                    //printf("j:%d u:%d part2:%d
",j,u,pre[j][0]);
                }
            }
        }
    }
}
void shuchu(int s,int e)
{
    //printf("here:%d %d
",s,e);
    if(s==e)
    {
        printf("%d ",s);
        return;
    }
    shuchu(s,pre[e][0]);
    printf("%d ",e);
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&st,&ed);
    int temp1,temp2,temp3,temp4;
    for(int i=0;i<=m-1;i++)
    {
        scanf("%d %d %d %d",&temp1,&temp2,&temp3,&temp4);
        G[temp1][temp2]=temp3;
        G[temp2][temp1]=temp3;
        cost[temp1][temp2]=temp4;
        cost[temp2][temp1]=temp4;
    }
    Dijkstra(st);
    /*for(int i=0;i<=n-1;i++)
        printf("%d ",pre[i][0]);*/
    shuchu(st,ed);
    printf("%d %d
",d[ed],c[ed]);
    return 0;
}

• 别忘了vector倒叙访问，如果不用迭代器，i=v.size()-1,end是给it用的
• 注意在根据d变化修改vector的时候不要忘了本来的d修改
• dfs中每次插入temp的是当前e点，sum中的是即将进入的下一轮e和当前e
• 加完了别忘了删除

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
int n,m,st,ed;
int G[1000][1000]={0},cost[1000][1000]={0};
int d[1000];
bool vis[1000]={false};
const int INF=10000;
vector<int>pre[1000];
void Dijkstra(int s)
{
    fill(d,d+n,INF);
    d[s]=0;
    for(int i=0;i<=n-1;i++)
    {
        int u=-1;
        int minnum=10000;
        for(int j=0;j<=n-1;j++)
        {
            if(vis[j]==false && d[j]<minnum)
            {
                u=j;
                minnum=d[j];
            }
        }
        if(u==-1)
            return;
        vis[u]=true;
        for(int j=0;j<=n-1;j++)
        {
            if(vis[j]==false && G[u][j]>0)
            {
                if(d[j]>d[u]+G[u][j])
                {
                    d[j]=d[u]+G[u][j];
                    //printf("no1 :%d
",j);
                    pre[j].clear();
                    pre[j].push_back(u);
                }
                else if(d[j]==d[u]+G[u][j])
                {
                    //printf("no2");
                    pre[j].push_back(u);
                }
            }
        }
    }
}
int nowsum=10000;
vector<int>ansroute;
vector<int>temproute;
void DFS(int s,int e,int sum)
{
    if(s==e)
    {
        if(sum<nowsum)
        {
            nowsum=sum;
            ansroute=temproute;
        }
        return;
    }
    for(int i=0;i<=pre[e].size()-1;i++)
    {
        temproute.push_back(e);
        DFS(s,pre[e][i],sum+cost[pre[e][i]][e]);
        temproute.erase(temproute.end()-1);
    }
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&st,&ed);
    for(int i=0;i<=m-1;i++)
    {
        int temp1,temp2,temp3,temp4;
        scanf("%d %d %d %d",&temp1,&temp2,&temp3,&temp4);
        G[temp1][temp2]=G[temp2][temp1]=temp3;
        cost[temp1][temp2]=cost[temp2][temp1]=temp4;
    }
    for(int i=0;i<=n-1;i++)
        pre[i].push_back(i);
    Dijkstra(st);
    DFS(st,ed,0);
    ansroute.push_back(st);
    for(int i=ansroute.size()-1;i>=0;i--)
        printf("%d ",ansroute[i]);
    printf("%d %d",d[ed],nowsum);
    return 0;
}

 凡是说马路，没有意外都是无向图，要双向赋值。