http://www.vijos.cn/Problem_Show.asp?id=1423
描述 Description
年久失修的赛道令国际汽联十分不满。汽联命令主办方立即对赛道进行调整，否则将取消其主办权.主办方当然必须马上开始行动。赛道测评人员经过了三天三夜的数据采集，选出了若干可以使用的道路和各道路行驶所需的时间。这些道路包括若干直道和弯道，每个直道连接两个不同的弯道且为单向,两个弯道之间可能有多条直道，通过直道和弯道都需要一定的时间。主办方打算在这些可用道路中选出一部分作为赛道。赛道是由直道和弯道交替组成的一圈，赛道可多次经过同一条弯道，因为主办方可以通过架设立交桥的方法避免撞车。为了使比赛更加精彩，主办方希望选择一条单圈时间最短的赛道,由于观众席的位置在弯道1，所以赛道必须经过弯道1(赛道至少要包含一条直道).
输入格式 Input Format
第一行是两个整数n，m(1<=n<=200，1<=m<=100000)，分别表示弯道数和直道数。接下来n行，第i行是一个整数ai(1<=ai<=1000)，表示通过第i个弯道所消耗的时间。接下来m行，第j行是三个整数xj，yj，bj(1& lt;=xj，yj<=n，1<=bj<=1000)，表示从弯道xj到弯道yj有一条单向直道，且通过该直道所消耗的时间为bj。
输出格式 Output Format
一个整数s，表示单圈时间最短的赛道的单圈时间，若无解则输出-1。
样例输入 Sample Input
【样例输入1】
3 6
1
1
2
1 2 3
2 3 5
3 1 1
3 2 1
2 1 10
1 3 15
【样例输入2】
3 4
1 1 2
1 2 4
1 3 5
2 3 5
3 2 10
样例输出 Sample Output
【样例输出1】
13
【样例输出2】
-1
时间限制 Time Limitation
各个测试点1s
分析：
删边+dijkstra
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int cost[210][210],d[210],a[210];
bool vis[210];
int n,m,ans;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(cost,0,sizeof(cost));
int x,y,c;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&c);
if (cost[x][y]==0 || cost[x][y]>c)
cost[x][y]=c;
}
int Min,p,temp;
ans=0x7FFFFFFF;
for (int i=1;i<=n;i++)
if (cost[1][i]!=0)
{
temp=cost[1][i]; cost[1][i]=0;
memset(d,127,sizeof(d));
memset(vis,false,sizeof(vis));
d[i]=0;
for (int j=1;j<=n-1;j++)
{
Min=0xFFFFFFF; p=0;
for (int k=1;k<=n;k++)
if (!vis[k] && d[k]<Min)
{
Min=d[k]; p=k;
}
if (p==0) break;
vis[p]=true;
for (int k=1;k<=n;k++)
if (cost[p][k]!=0 && !vis[k] && d[k]>d[p]+cost[p][k]+a[k])
d[k]=d[p]+cost[p][k]+a[k];
}
cost[1][i]=temp;
if (ans>cost[1][i]+a[i]+d[1])
ans=cost[1][i]+a[i]+d[1];
}
if (ans<2100000000) printf("%d\n",ans);
else printf("-1\n");
return 0;
}