Problem #1817 - ECNU Online Judge

ShengHua

6 年，4 月前

这道题WA了十几次，然后发现因为是有向图我当成无向图去做了

Andrew-Malcom

4 年前

Dijkstra算法
#include<bits/stdc++.h>
using namespace std;
const int maxn=1001;
const int INF=0x3f3f3f;
typedef struct _graph{
    int edge;
    int vex;
    int martix[maxn][maxn];
}Graph,*pGraph;
void dijkstra(int dis[],int pre[],int start,Graph G)
{
    int sum=G.vex;
    bool visited[G.vex+10];
    for(int i=1;i<=G.vex;i++){
        dis[i]=INF;
        visited[i]=false;
        pre[i]=0;
        if(G.martix[start][i]!=0) dis[i]=G.martix[start][i];
    }
    dis[start]=0;visited[start]=true;sum--;
    while(sum>0){
        int mind=INF,k;
        for(int i=1;i<=G.vex;i++){
            if(visited[i]==false){
                if(dis[i]<=mind){
                    mind=dis[i];
                    k=i;
                }
            }
        }
        visited[k]=true;sum--;
        for(int i=1;i<=G.vex;i++){
            if(visited[i]==false&&G.martix[k][i]!=0){
                dis[i]=min(dis[i],mind+G.martix[k][i]);
                pre[i]=k;
            }
        }
    }
}
int main()
{
    Graph G;memset(G.martix,0,sizeof(G.martix));
    int n,m;cin>>n>>m;
    G.vex=n;G.edge=m;
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        G.martix[u][v]=w;
    }
    int dis[n+10],pre[n+10];
    dijkstra(dis,pre,1,G);
    printf("%d",(dis[n]==INF)?-1:dis[n]);
}

回复 1 0

Andrew-Malcom

4 年前

dp做法
#include<bits/stdc++.h>
#define FUCK ios::sync_with_stdio(false);
using namespace std;
int main()
{
    FUCK;cin.tie(0);
    int n,m;cin>>n>>m;
    int grath[n+1][n+1]={0},dp[n+1][n+1]={0};
    int i,j,k;
    for(k=0;k<m;k++){
        int u,v,w;cin>>u>>v>>w;
        grath[u][v]=w;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(i!=j){
                int MAX=1e8+50;
                for(k=1;k<=n;k++){
                    if(grath[k][j]!=0&&grath[k][j]+dp[i][k]<=MAX){
                        MAX=grath[k][j]+dp[i][k];
                    }
                }
                dp[i][j]=MAX;
            }
            else if(i==j) dp[i][j]=0;
        }
    }
    if(dp[1][n]==1e8+50) cout<<-1;
    else cout<<dp[1][n];
}

回复 1 0

一剑无痕雪满山

7 年，6 月前

只会用书上的方法……
完全抄书……就是那个最大值需要定的大一点嗯

include

define MAXINT 9999999

define MAXN 1800

typedef int MAT[MAXN][MAXN];
MAT cost;
int dist[MAXN];int pre[MAXN];int n,v;
void shortestpath(MAT cost,int n,int v,int dist[],int pre[])
{
int s[MAXN],j,k,i,min;
for(i=1;i<=n;i++)
{
dist[i]=cost[v][i];
s[i]=0;
if(dist[i]<MAXINT)
pre[i]=v;
else pre[i]=0; //初始化pre数组

}
s[v]=1;
pre[v]=0;
for(i=1;i<=n;i++)
{
    min=MAXINT;
    k=0;
    for(j=1;j<=n;j++)
    {
        if(s[j]==0)
        {
            if(dist[j]!=0&&dist[j]<min)
            {min=dist[j];k=j;}
        }
    }
    if(k==0) continue;
    s[k]=1;
    for(j=1;j<=n;j++)
   {
    if(s[j]==0&&cost[k][j]<MAXINT)
    {
        if(dist[k]+cost[k][j]<dist[j])
        {dist[j]=dist[k]+cost[k][j];pre[j]=k;}
    }
   }
}

if(dist[n]<MAXINT) printf(“%d\n”,dist[n]);
else printf(“-1\n”);
}

int main()
{
int m;int i;
int u1,v1,w;
scanf(“%d%d”,&n,&m);
memset(cost,MAXINT,sizeof(cost));
for(i=1;i<=m;i++)
{
scanf(“%d%d%d”,&u1,&v1,&w);
cost[u1][v1]=w;
}
for(i=1;i<=n;i++)
{
cost[i][i]=0;
}
shortestpath(cost,n,1,dist,pre);
return 0;
}

回复 0 0

lnu_cxn

4 年，5 月前

include

using namespace std;

define max 1e6

int s[600][600]={0};
bool visit[600]={false};
int main(){
for(int i=0;i<600;i++)
for(int j=0;j<600;j++)
s[i][j]=max;
int n,m;
cin>>n>>m;
for(int i=0;i>temp1>>temp2>>temp3;
s[temp1][temp2]=temp3;
}
for(int i=2;i<=n;i++){
int min=max,temp;
for(int j=1;j<=n;j++)
if(!visit[j]&&s[1][j]<min){
min=s[1][j];
temp=j;
}
visit[temp]=true;
for(int j=1;j<=n;j++)
if(!visit[j]&&s[1][temp]+s[temp][j]<s[1][j])
s[1][j]=s[1][temp]+s[temp][j];
}
if(s[1][n]==max)
cout<<”-1”<<endl;
else
cout<<s[1][n]<<endl;
return 0;
}

回复 0 0

Luckywei233

4 年，5 月前

include

define MAX 0xffff

using namespace std;
int graph[601][601];
int floyd(int n) {
for (int i = 1; i < n; i++)
for (int j = 1; j < n; j++)
graph[0][j] = graph[0][j] < graph[i][j] + graph[0][i] ? graph[0][j] : graph[0][i] + graph[i][j];
return graph[0][n - 1];
}
int main() {
int n, x;
cin >> n >> x;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j)graph[i][j] = MAX;
}
}
for (int i = 0; i < x; i++) {
int a, b, w;
cin >> a >> b >> w;
graph[a - 1][b - 1] = w;
}
int result = floyd(n);
cout << ((result<MAX)?result:-1) << endl;
return 0;
}

回复 0 1

1817. 最短路径

include

include

include

define MAXINT 9999999

define MAXN 1800

include

define max 1e6

include

define MAX 0xffff

服务

开源

关于我们