1379. Cups Transportation
2067 단어 port
이분 최 단 로
코드:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#define LL long long
#define sint short int
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N=505;
const int T=1440;
const int INF=1000000000;
int head[N],I;
bool had[N];
int dist[N];
int cost[N][N];
int limi[N][N];
int dijkstra(int x1,int x2,int n,int limit)
{
for(int i=1;i<=n;++i)
dist[i]=INF;
memset(had,false,sizeof(had));
dist[x1]=0;
for(int w=1;w<=n;++w)
{
int k=-1;
for(int i=1;i<=n;++i)
if(!had[i]&&(k==-1||dist[i]<dist[k]))
k=i;
if(k==x2||dist[k]==INF)
break;
had[k]=true;
for(int i=1;i<=n;++i)
if(!had[i]&&limi[k][i]>=limit&&dist[k]+cost[k][i]<dist[i])
dist[i]=dist[k]+cost[k][i];
}
return dist[x2];
}
int main()
{
//freopen("data.in","r",stdin);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{limi[i][j]=0;cost[i][j]=INF;}
int l=1,r=0;
while(m--)
{
int i,j,t,g;
cin>>i>>j>>t>>g;
g=max((g-3000000)/100,0);
cost[i][j]=cost[j][i]=t;
limi[i][j]=limi[j][i]=g;
r=max(r,g);
}
if(n==1)
{cout<<"10000000"<<endl;return 0;}
while(l<=r)
{
int mid=(l+r)/2;
if(dijkstra(1,n,n,mid)<=T)
l=mid+1;
else
r=mid-1;
}
cout<<r<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
시스템 의 상황 을 감시 하고 당신 이 알 아야 할 두 세 가지!좀 비 프로 세 스, CPU 의 이 용 률, 메모리 의 사용 상황, 디스크 공간의 사용 상황, 시스템 의 균형 부하 보다 못 합 니 다. 최신 정보 에 따라 시스템 운행 상태 가 좋 은 지 판단 할 수 있 습 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.